STOC 2020 Workshop: Derandomizing Space-Bounded Computation
Time and Date: 10:00 PDT to 13:00 PDT, Friday, June 26, 2020.
Organizers: Raghu Meka (raghum@cs.ucla.edu), Avishay Tal (atal@berkeley.edu), and David Zuckerman (diz@utexas.edu)
Description: A major question in computer science asks what is the power of randomness in computation? Does BPP=P? However, the BPP versus P problem entails proving strong lower bounds, so probably the most exciting prospect of a big unconditional derandomization result is that BPL=L. This would imply BPSPACE(S)=DSPACE(S) for any space-constructible S(n) >= log(n). Despite much effort, we still don’t know any better theorem than BPL in L3/2, proved by Saks and Zhou over 20 years ago. On the other hand, there has recently been some exciting progress in several related directions. That’s the focus of this workshop.
Goals: The goals of this workshop are to understand these new directions. They include new pseudorandom generators (PRGs) using pseudorandom restrictions, including PRGs for any-order read-once branching programs and product tests; constructions of hitting sets and newly defined “pseudorandom pseudo-distributions” that have optimal dependence on the error; and a new approach based on Laplacian solvers. The talks are aimed to be accessible to non-experts, and informative to experts.
Schedule:
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
Abstracts:
Pseudorandom Generators via Pseudorandom Restrictions
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.
Pseudorandom Generators for Read-Once Branching Programs, in any Order
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.
A recent line of inquiry has suggested focusing on a particular limitation of the existing PRGs, which is that they only fool roBPs when the variables are read in a particular *known* order, such as x_1<...<x_n.
In comparison, existentially one can obtain logarithmic seed-length for fooling the set of polynomial-size roBPs that read the variables under any fixed *unknown* permutation x_{pi(1)}<...<x_{pi(n)}. While recent works have established novel PRGs in this setting for subclasses of roBPs, there were no known n^{o(1)} seed-length explicit PRGs for general polynomial-size roBPs in this setting.
In this work, we follow the "bounded independence plus noise" paradigm of Haramaty, Lee and Viola, and give an improved analysis in the general roBP unknown-order setting. With this analysis we obtain an explicit PRG with seed-length O(log^3 n) for polynomial-size roBPs reading their bits in an unknown order. Plugging in a recent Fourier tail bound of Chattopadhyay, Hatami, Reingold, and Tal, we can obtain a ~O(log^2 n) seed-length when the roBP is of constant width.
Joint work with Zander Kelley.
Pseudorandom Pseudo-Distributions with Near-Optimal Error for Read-Once Branching Programs
Sumegha Garg, Princeton University
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 Solvers
Salil 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.