10:00 - 10:40 (PDT) - Avishay Tal -- PRGs via Pseudorandom Restrictions 10:45 - 11:25 (PDT) - Michael A. Forbes -- PRGs for Read-Once Branching Programs, in any Order 11:25 - 11:35 (PDT) - Break 11:35 - 12:15 (PDT) - Sumegha Garg -- Pseudorandom Pseudo-Distributions with Near-Optimal Error for Read-Once Branching Programs 12:20 - 1:00 (PDT) - Salil Vadhan -- Derandomizing Space-Bounded Computation via Laplacian Solvers
Avishay Tal, University of California, Berkeley
Can we derandomize computation without increasing the memory footprint? This is essentially the RL vs. L question. A major approach towards this goal is to construct pseudorandom generators (PRGs) with O(log n) seed-length that fool log-space computation. Despite many efforts, this approach has been stuck at the O(log^2(n)) barrier for three decades now, since the seminal result of Nisan.
I will survey some recent work from the last decade that revived the restrictions-based PRG approach of Ajtai and Wigderson (which predates Nisan's PRG!). The idea is as follows. Numerous results in complexity theory show that certain classes of Boolean functions become simpler under random restrictions (most notably "Håstad's Switching Lemma" for AC0 circuits). Ajtai and Wigderson show that it suffices to fool the restricted (simpler) function to get a PRG for the original (more complicated) function. This is achieved via a recursive approach, where one partitions the bits pseudorandomly to buckets and then picks pseudorandomly values for each bucket. This approach was revived and strengthened in the beautiful work of Gopalan, Meka, Reingold, Trevisan, and Vadhan. GMRTV observed that it suffices to fool the average of the restricted functions, instead of fooling each one individually -- an easier task in many cases. GMRTV approach led to a nearly optimal PRG for read-once DNF/CNF formulae, combinatorial rectangles, and more. In the realm of small-space computation, this PRG almost matches the state-of-the-art PRGs by Nisan and INW (to be highlighted in Michael's talk), and in some special cases, even surpasses it. Understanding the full power and limitations of this PRG remains open.
Michael A. Forbes, University of Illinois at Urbana-Champaign A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length O(log^2 n) were constructed. Unfortunately, improving on this seed-length in general has proven challenging and seems to require new ideas.
Nisan [Nis92] constructed a pseudorandom generator for length n, width w read-once branching programs (ROBPs) with error ε and seed length O(log^2 n + log n · log w + log n · log(1/ε)). Informally, a pseudorandom generator with seed length s specifies 2^s paths such that for any length n, width w ROBP, the probability of acceptance (over 2^n paths) can be approximated, upto error ε, by the fraction of these 2^s paths that are accepting. A major goal in complexity theory is to reduce the seed length, hopefully, to O(log nw/ε)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL (randomized log-space computation with two-sided error) and RL (randomized log-space computation with one-sided error), respectively. In contrast to a successful line of work in restricted settings, for general unrestricted ROBPs (for n=w), no progress had been made since [Nis92]. A recent line of work [BCG'18, HZ'18, CL'20] made improvements for the general case by constructing hitting sets and pseudorandom pseudo-distributions with optimal dependence on ε (seed length ~O(log^2 n + log n · log w + log(1/ε))). The regime of parameters in which these constructions strictly improve upon prior works, namely, log(1/ε) ≫ log n, is also motivated by the work of Saks and Zhou [SZ99] who use pseudorandom generators with error ε, for length n, width w read-once branching programs, such that w, 1/ε = 2^(log^2 n) in their proof for BPL ⊆ L^3/2. In this talk, we survey this line of work and focus on the starting work of [BCG'18]. In this work, we introduce and construct a new type of primitive called pseudorandom pseudo-distributions. Informally, this is a generalization of pseudorandom generators in which one may assign negative and unbounded weights to paths as opposed to working with probability distributions. We show that such a primitive yields hitting sets and, for derandomization purposes, can be used to derandomize two-sided error algorithms. Joint work with Mark Braverman and Gil Cohen (STOC'18). Derandomizing Space-Bounded Computation via Laplacian SolversSalil Vadhan, Harvard University
I will describe a series of works that attacks the derandomization of space-bounded computation (e.g. seeking to prove BPL=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, for Eulerian directed graphs and hence also undirected graphs, 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. 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). Extending these results to general directed graphs (as was done in the time-bounded case) would suffice to derandomize all of BPL. Joint works with Murtagh, Reingold, and Sidford (FOCS `17 and RANDOM `19) and Ahmadinejad, Kelner, Murtagh, Peebles, and Sidford (arXiv `19). Another excellent resource is this two-part tutorial lectures by Omer Reingold about the same topic from CCC 2019. |