ST-Connectivity in Log-Space
papers on the zig-zag product:
- O. Reingold, S. Vadhan, A. Wigderson.
Waves, The Zig-Zag
Graph Product, and New Constant-Degree Expanders and Extractors.
FOCS `00, ECCC `01, DIMACS TR `01, Annals of Math `02.
- M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson.
Conductors and Constant-Degree Lossless Expanders.
attempt to extend the method to directed graphs.
best result currently known for RL (but for how long)?
- BP H SPACE (S)⊆ DSPACE (S 3/2)
M Saks, S Zhou - Cited by 4
... Pages: 376 - 403. Year of Publication: 1999. ISSN:0022-0000. Authors, Michael Saks,
Shiyu Zhou, Publisher, Academic Press,
Inc. Orlando, FL, USA. ...
Journal of Computer and System Sciences, 1999 -
J.-Y. Cai, V. Chakaravarthy, and D. van Melkebeek.
Time-Space Tradeoff In Derandomizing Probabilistic Logspace.
In Proceedings of the 21st International Symposium on
Theoretical Aspects of Computer
Science, pages 571-583, 2004.
best space-algorithm for directed stcon known today,
running in polynomial time.
matching lower bound? The NNJAG model.
- J. A. Edmonds and C. K. Poon. A nearly
optimal time-space lower bound for directed st-
connectivity on the NNJAG model. In Proceedings of the Twenty-Seventh
Annual ACM Symposium on Theory of Computing, pages 147--156, Las Vegas,
NV, May 1995.
old result on undirected connectivity, that is subsumed by Omer, but we may
learn from it anyway.
Undiercted Connectivity in
by N. Nisan E. Szemeredi and A. Wigderson.
Derandomization that is Rarely Wrong from Short
Advice that is Typically Good
Randomization and Approximation
Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp.
[ Draft of final version (postscript) ] [ Draft of final version (pdf) ]
$\NC$ Algorithm for Minimum Cuts by David R. Karger,
SIAM Journal on
Volume 26, Number 1 pp.
PostScript document (27308.ps: 622320 bytes)
PDF document (27308.pdf: 332827 bytes)
surprising use of PRG for low space, and an open problem