When Connectivity is Hard, Random Walks are Easy (with Nondeterminism)

Title: When Connectivity is Hard, Random Walks are Easy (with Nondeterminism)

Abstract: Two well-studied graph problems are to 1: determine connectivity, and 2: estimate the behavior of random walks. Currently, there is no algorithm which solves (1) in polynomial time and strongly sublinear space, and no algorithm for (2) that runs in nondeterministic logspace.

We show that for every graph, at least one of these problems is solvable more efficiently than the state of the art. Our results build on recent work on distinguish-to-predict transformations (Li, Pyne, Tell) and bootstrapping systems (Chen, Tell). As a consequence, either randomized linear space can be derandomized, or a time- and space- efficient simulation of nondeterministic linear space holds. 

Joint work with Dean Doron, Roei Tell, and Ryan Williams (to appear STOC 2025).

Bio: Ted a third-year graduate student at MIT, advised by Ryan Williams and Ronitt Rubinfeld. He is interested in derandomization, catalytic computation, and graph algorithms.