Salil Vadhan: Derandomizing Algorithms via Spectral Graph Theory

Abstract: Randomization is a powerful tool for algorithms; it is often easier to design efficient algorithms if we allow the algorithms to "toss coins" and output a correct answer with high probability. However, a longstanding conjecture in theoretical computer science is that every randomized algorithm can be efficiently "derandomized" --- converted into a deterministic algorithm (which always outputs the correct answer) with only a polynomial increase in running time and only a constant-factor increase in space (i.e. memory usage).
In this talk, I will describe an approach to proving the space (as opposed to time) part of this conjecture via spectral graph theory. Specifically, I will explain how randomized space-bounded algorithms are described by random walks on directed graphs, and techniques in algorithmic spectral graph theory (e.g. solving Laplacian systems) have yielded deterministic space-efficient algorithms for approximating the behavior of such random walks on undirected graphs and Eulerian directed graphs (where every vertex has the same in-degree as out-degree). If these algorithms can be extended to general directed graphs, then the aforementioned conjecture about derandomizing space-efficient algorithms will be resolved. These problems also lead us to explore new notions of what it means for two directed graphs to "spectrally approximate" each other, which may be of independent interest.
SMRI events mentioned:
"Perspectives on Mathematics" special semester (organised by Francis Su): 1 March - 31 May 2024
sites.google.com/view/perspec...
IMU-SMRI Mathematical Colloquia and Panels: 25-26 March 2024 at the University of Sydney
mathematical-research-institu...