SMRI Seminar ’Derandomizing Algorithms via Spectral Graph Theory’ Salil Vadhan (Harvard University) Date and time: Thursday 21st March, 13:00-14:00 AEDT Location: Law Annex Lecture Theatre 026 and online Register/join for online attendance: https://uni-sydney.zoom.us/j/82043554503 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. Joint works with Jack Murtagh, Omer Reingold, Aaron Sidford, AmirMadhi Ahmadinejad, Jon Kelner, John Peebles, and Ted Pyne. ---- Please join us after the seminar for SMRI afternoon tea, 2:00-2:45pm every Thursday on the SMRI Terrace (accessed through A14-04-L4.36) ---- Current and past seminar info (including recordings) can be found on the seminars webpage. Other upcoming SMRI events can be found here: https://mathematical-research-institute.sydney.edu.au/news-events/ SMRI YouTube Channel: https://youtube.com/@SydMathInst