BEGIN:VCALENDAR
BEGIN:VEVENT
SUMMARY:Theory Lunch
DESCRIPTION:Speaker: Salil Vadhan, Harvard University
Talk Title: Derandomization Beyond Connectivity: High-Precision Estimation of Random Walks and Laplacian Solvers in Small Space
Abstract: I will describe a series of works that attacks the derandomization of space-bounded computation (e.g. seeking to prove RL=L) using a combination of ideas from the literature on time-efficient 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 S-T Connectivity is in deterministic logspace (Reingold, STOC '05 and JACM '08; Rozenman and Vadhan, RANDOM '05).\n
\n
In particular, we obtain deterministic, nearly logarithmic-space 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 Ta-Shma RANDOM '17), and hence by deterministic algorithms using space O(log^{3/2} N) (Saks and Zhou, FOCS '95 and JCSS '99).\n
\n
Joint works with Murtagh, Reingold, and Sidford (FOCS '17 and RANDOM '19) and Ahmadinejad, Kelner, Murtagh, Peebles, and Sidford (arXiv:1912.04524)\n
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 zero-knowledge proofs. His work on zig-zag product, with Omer Reingold and Avi Wigderson, was awarded the 2009 Gödel Prize.
Host: Shaddin Dughmi
DTSTART:20200213T121500
LOCATION:SAL 213
URL;VALUE=URI:
DTEND:20200213T140000
END:VEVENT
END:VCALENDAR