דין דורון

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₁ and A₂ such that for every graph G, either: A₁(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A₂(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.