Derandomizing Algorithms via Spectral Graph Theory

CMSA EVENTS: CMSA COLLOQUIUM

When: March 4, 2020
4:45 pm - 5:45 pm
Where: CMSA, 20 Garden St, G10
Address: 20 Garden Street, Cambridge, MA 02138, United States
Speaker: Salil Vadhan - Harvard University
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) version 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.

Joint works with Jack Murtagh, Omer Reingold, Aaron Sidford,  AmirMadhi Ahmadinejad, Jon Kelner, and John Peebles.