Events Calendar

Theory Lunch

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).

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).

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 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

Location: Henry Salvatori Computer Science Center (SAL) - 213

Audiences: Everyone Is Invited

Contact: Cherie Carter