Computer Science/Discrete Mathematics Seminar III

Undirected st-connectivity (USTCONN) is the problem of checking whether two given vertices of an undirected graph are connected by a path. Solving USTCONN in space O(log n), and even o(log2 n), is a challenging task. A randomized logspace algorithm for USTCONN due to Aleliunas et al. was known for a long time. Interest in USTCONN comes from the fact that it is complete for a class of problems between L and NL, and its directed version is NL-complete. Since understanding the power of non-determinism over determinism presents a major challenge to complexity theory it is important to study classes between L and NL, the smallest natural classes capturing deterministic and non-deterministic space-efficient computation. In this talk we present our work on an algorithm solving USTCONN in space O(log n log log n) by simulating non-trivially an efficient parallel algorithm for USTCONN due to Chong and Lam. This approach differs significantly from the approaches attempted in the past, which used in some form the ideas behind the randomized algorithm of Aleliunas et al. The simulation uses exploration walks on trees defined by Koucky. Our bound is an improvement over the previous bound of O(log^{4/3} n) due to Armoni et al. and a significant step towards the optimal O(log n) bound. The optimal bound was obtained recently by Reingold with different set of techniques.