# CMSA Colloquium: Derandomizing Algorithms via Spectral Graph Theory

CMSA EVENTS

##### Speaker:

Salil Vadhan *- Harvard University*

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.