SMS scnews item created by Hannah Bryant at Mon 18 Mar 2024 1316
Type: Seminar
Modified: Mon 18 Mar 2024 1508
Distribution: World
Expiry: 21 Mar 2024
Calendar1: 21 Mar 2024 1300-1400
CalLoc1: Law Annex Lecture Theatre 026 & Online
CalTitle1: SMRI Seminar: ’Derandomizing Algorithms via Spectral Graph Theory’ Salil Vadhan (Harvard University)
Auth: (hbry8683) in SMS-SAML

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:

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

Other upcoming SMRI events can be found here: 

SMRI YouTube Channel:

ball Calendar (ICS file) download, for import into your favourite calendar application
ball UNCLUTTER for printing
ball AUTHENTICATE to mark the scnews item as read
School members may try to .