For every $\epsilon>0$, we present a {\em deterministic}\/ log-space algorithm that correctly decides undirected graph connectivity on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs. The same holds for every problem in Symmetric Log-space (i.e., $\SL$). Making no assumptions (and in particular not assuming the ERH), we present a ... more >>>

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), ... more >>>