SMRI Seminar: Vadhan -- Derandomizing Algorithms via Spectral Graph Theory

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