*    USTCON in LogSpace


Undirected ST-Connectivity in Log-Space  

Omer Reingold


*    Two papers on the zig-zag product:

*    An attempt to extend the method to directed graphs.

*    The 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 -

Also relevant:
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.




*    The best space-algorithm for directed stcon known today, running in polynomial time.


*    A 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.

*    An old result on undirected connectivity, that is subsumed by Omer, but we may learn from it anyway.


 Undiercted Connectivity in log^1.5(n) space
by N. Nisan E. Szemeredi and A. Wigderson.


*    A cute idea:

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. 209-223, 2002

(Abstract) [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]



*     An $\NC$ Algorithm for Minimum Cuts by David R. Karger, Rajeev Motwani

SIAM Journal on Computing
Volume 26, Number 1 pp. 255-272

gunzipedRetrieve PostScript document ( 622320 bytes)

Retrieve PDF document (27308.pdf: 332827 bytes)


*    A surprising use of PRG for low space, and an open problem