When Connectivity Is Hard, Random Walks Are Easy with Non-determinism

Two fundamental problems on directed graphs are to decide 𝑠-𝑡 connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for 𝑠-𝑡 connectivity running in polynomial time and 𝑛 𝑜 (1) space, and no known algorithm for estimating the 𝑛-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 𝐴 1 and 𝐴 2 such that for every graph 𝐺, either:

(1) 𝐴 1 (𝐺) outputs the transitive closure of 𝐺 in polynomial time and polylogarithmic space. (2) 𝐴 2 (𝐺) outputs an approximation of the 𝑛-step random walk matrix of 𝐺 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 hardnessvs.-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