A celebrated theorem of Savitch states that NSPACE(S) is contained DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitch’s theorem itself has not been improved in the last four decades, studying the space complexity of ... more >>>

Two fundamental problems on directed graphs are to decide $s$-$t$ connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for $s$-$t$ connectivity running in polynomial time and $n^{o(1)}$ space, and no known algorithm for estimating the $n$-step random walk matrix running in non-deterministic logspace. ... more >>>