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.
We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms $A_1$ and $A_2$ such that for every graph $G$, either:
1: $A_1(G)$ outputs the transitive closure of $G$ in polynomial time and polylogarithmic space.
2: $A_2(G)$ outputs an approximation of the $n$-step random walk matrix of $G$ in non-deterministic logspace.
As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch's theorem can be non-trivially sped up, or randomized space can be almost completely derandomized.
We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron--Pyne--Tell STOC 2024, Li--Pyne--Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron--Tell CCC 2024).
To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel--Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen--Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting.
