
Theory Lunch
Thu, Feb 13, 2020 @ 12:15 PM  02:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Salil Vadhan, Harvard University
Talk Title: Derandomization Beyond Connectivity: HighPrecision Estimation of Random Walks and Laplacian Solvers in Small Space
Abstract: I will describe a series of works that attacks the derandomization of spacebounded computation (e.g. seeking to prove RL=L) using a combination of ideas from the literature on timeefficient Laplacian solvers (Spielman and Teng, STOC '04; Peng and Spielman, STOC '14; Cheng et al. '15; Cohen et al. FOCS '16, STOC '17, FOCS '18) with ones used to show that Undirected ST Connectivity is in deterministic logspace (Reingold, STOC '05 and JACM '08; Rozenman and Vadhan, RANDOM '05).
In particular, we obtain deterministic, nearly logarithmicspace algorithms for (a) estimating random walk probabilities to within polynomially small error and (b) approximately solving linear systems given by graph Laplacians, with both results holding for Eulerian directed graphs and hence also undirected graphs. Previously both of these problems were known to be solvable for general directed graphs by randomized algorithms in logarithmic space (Aleliunas et al. FOCS '79; Doron, Le Gall, and TaShma RANDOM '17), and hence by deterministic algorithms using space O(log^{3/2} N) (Saks and Zhou, FOCS '95 and JCSS '99).
Joint works with Murtagh, Reingold, and Sidford (FOCS '17 and RANDOM '19) and Ahmadinejad, Kelner, Murtagh, Peebles, and Sidford (arXiv:1912.04524)
Biography: Salil Vadhan is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. After completing his undergraduate degree in Mathematics and Computer Science at Harvard in 1995, he obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology in 1999, where his advisor was Shafi Goldwasser. His research centers around the interface between computational complexity theory and cryptography. He focuses on the topics of pseudorandomness and zeroknowledge proofs. His work on zigzag product, with Omer Reingold and Avi Wigderson, was awarded the 2009 GÃ¶del Prize.
Host: Shaddin Dughmi
Location: Henry Salvatori Computer Science Center (SAL)  213
Audiences: Everyone Is Invited
Contact: Cherie Carter