• Calendar

April 5, Tuesday
12:00 – 14:00

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was $\log^{4/3}()$ obtained by Armoni, Ta-Shma, Wigderson and Zhou.

As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that $SL=L$ (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov has presented a, space $\log n \log\log n$, deterministic algorithm for undirected st-connectivity.

Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.