Spectral Graph-Theoretic Methods for Derandomizing Space-Bounded Computation

Abstract

While randomness can seem like an indispensable resource in algorithm development, it is widely believed that all algorithms for standard problems can be made deterministic with only a polynomial time slowdown and constant factor increase in space usage. Proving such a result unconditionally is a major goal of computational complexity theory. We study this question in the space-bounded setting, where space-bounded algorithms are those whose memory usage is logarithmic or nearly logarithmic in their input size. One approach to derandomizing space-bounded computation is graph-theoretic in nature and there is a rich history of research progress using increasingly sophisticated graph-theoretic techniques to provide further evidence that randomness is not needed for space-efficiency. In a parallel, seemingly disparate line of work, powerful spectral graph-theoretic methods known collectively as “The Laplacian Paradigm” have been developed in the context of nearly linear-time randomized graph algorithms over the past 15 years. In this thesis, we merge these two beautiful lines of work and show that the aforementioned spectral graph-theoretic techniques are not only compatible with the deterministic small space setting, but yield a number of new insights and results in derandomization. Our main results are new derandomizations for increasingly rich graph-theoretic problems. In particular, we give deterministic, nearly logarithmic-space algorithms for: 1. Approximately solving Laplacian systems, 2. Approximating hitting times, commute times, and escape probabilities, 3. Approximating random walk probabilities, 4. Computing spectral sparsifiers. We achieve the first three items in both undirected and, more generally, Eulerian directed graphs. The last three items all make critical use of our space-efficient Laplacian solvers from item 1. In addition to the new space-efficient derandomizations above, we also get improvements to algorithms in other complexity regimes, including randomized nearly linear-time, randomized logarithmic-space, and deterministic polylogarithmic-space. Our work demonstrates the power of spectral graph theory for space-bounded derandomization and we believe the machinery developed in this thesis will continue to find applications in this growing research area.