 Award ID(s):
 2145474
 NSFPAR ID:
 10484211
 Editor(s):
 Etessami, Kousha; Feige, Uriel; Puppis, Gabriele
 Publisher / Repository:
 Schloss Dagstuhl – LeibnizZentrum für Informatik
 Date Published:
 Subject(s) / Keyword(s):
 pseudorandom generators derandomization readonce branching programs Theory of computation → Pseudorandomness and derandomization
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Guruswami, Venkatesan (Ed.)In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular readonce branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of spacebounded derandomization, which was originally introduced by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford and Vadhan (FOCS 2020). In this work, we give an alternative error reduction framework for regular ROBPs. Our new framework is based on a binary recursive formula from the work of Chattopadhyay and Liao (CCC 2020), that they used to construct weighted pseudorandom generators (WPRGs) for general ROBPs. Based on our new error reduction framework, we give alternative proofs to the following results for regular ROBPs of length n and width w, both of which were proved in the work of Chen et al. using their error reduction:  There is a WPRG with error ε that has seed length Õ(log(n)(√{log(1/ε)}+log(w))+log(1/ε)).  There is a (nonblackbox) deterministic algorithm which estimates the expectation of any such program within error ±ε with space complexity Õ(log(nw)⋅log log(1/ε)). This was first proved in the work of Ahmadinejad et al., but the proof by Chen et al. is simpler. Because of the binary recursive nature of our new framework, both of our proofs are based on a straightforward induction that is arguably simpler than the Laplacianbased proof in the work of Chen et al. In fact, because of its simplicity, our proof of the second result directly gives a slightly stronger claim: our algorithm computes a εsingular value approximation (a notion of approximation introduced in a recent work by Ahmadinejad, Peebles, Pyne, Sidford and Vadhan (FOCS 2023)) of the random walk matrix of the given ROBP in space Õ(log(nw)⋅log log(1/ε)). It is not clear how to get this stronger result from the previous proofs.more » « less

Saraf, Shubhangi (Ed.)There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The "iterated restrictions" approach, pioneered by Ajtai and Wigderson [Ajtai and Wigderson, 1989], has provided PRGs with seed length polylog n or even Õ(log n) for several restricted models of computation. Can this approach ever achieve the optimal seed length of O(log n)? In this work, we answer this question in the affirmative. Using the iterated restrictions approach, we construct an explicit PRG for readonce depth2 AC⁰[⊕] formulas with seed length O(log n) + Õ(log(1/ε)). In particular, we achieve optimal seed length O(log n) with nearoptimal error ε = exp(Ω̃(log n)). Even for constant error, the best prior PRG for this model (which includes readonce CNFs and readonce 𝔽₂polynomials) has seed length Θ(log n ⋅ (log log n)²) [Chin Ho Lee, 2019]. A key step in the analysis of our PRG is a tail bound for subsetwise symmetric polynomials, a generalization of elementary symmetric polynomials. Like elementary symmetric polynomials, subsetwise symmetric polynomials provide a way to organize the expansion of ∏_{i=1}^m (1 + y_i). Elementary symmetric polynomials simply organize the terms by degree, i.e., they keep track of the number of variables participating in each monomial. Subsetwise symmetric polynomials keep track of more data: for a fixed partition of [m], they keep track of the number of variables from each subset participating in each monomial. Our tail bound extends prior work by Gopalan and Yehudayoff [Gopalan and Yehudayoff, 2014] on elementary symmetric polynomials.more » « less

Abstract The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for spacebounded computation uses a seed of length
to fool ordered branching programs of length$$O(\log n \cdot \log (nw/\varepsilon )+\log d)$$ $O(logn\xb7log(nw/\epsilon )+logd)$n , widthw , and alphabet sized to within error . A series of works have shown that the analysis of the INW generator can be improved for the class of$$\varepsilon $$ $\epsilon $permutation branching programs or the more generalregular branching programs, improving the dependence on the length$$O(\log ^2 n)$$ $O\left({log}^{2}n\right)$n to or$$O(\log n)$$ $O(logn)$ . However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length$${\tilde{O}}(\log n)$$ $\stackrel{~}{O}(logn)$ . In this paper, we prove that any “spectral analysis” of the INW generator requires seed length$$O(\log (nwd/\varepsilon ))$$ $O(log(nwd/\epsilon \left)\right)$ to fool ordered permutation branching programs of length$$\begin{aligned} \Omega \left( \log n\cdot \log \log \left( \min \{n,d\}\right) +\log n\cdot \log \left( w/\varepsilon \right) +\log d\right) \end{aligned}$$ $\begin{array}{c}\Omega \left(log,n,\xb7,log,log,\left(min,\{,n,,,d,\}\right),+,log,n,\xb7,log,\left(w,/,\epsilon \right),+,log,d\right)\end{array}$n , widthw , and alphabet sized to within error . By “spectral analysis” we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman–Rao–Raz–Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size$$\varepsilon $$ $\epsilon $ except for a gap between their$$d=2$$ $d=2$ term and our$$O\left( \log n \cdot \log \log n\right) $$ $O\left(log,n,\xb7,log,log,n\right)$ term. It also matches the upper bounds of Koucký–Nimbhorkar–Pudlák (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constantwidth ($$\Omega \left( \log n \cdot \log \log \min \{n,d\}\right) $$ $\Omega \left(log,n,\xb7,log,log,min,\{,n,,,d,\}\right)$ ) permutation branching programs of alphabet size$$w=O(1)$$ $w=O\left(1\right)$ to within a constant factor. To fool permutation branching programs in the measure of$$d=2$$ $d=2$spectral norm , we prove that any spectral analysis of the INW generator requires a seed of length when the width is at least polynomial in$$\Omega \left( \log n\cdot \log \log n+\log n\cdot \log (1/\varepsilon )\right) $$ $\Omega \left(log,n,\xb7,log,log,n,+,log,n,\xb7,log,(,1,/,\epsilon ,)\right)$n ( ), matching the recent upper bound of Hoza–Pyne–Vadhan (ITCS 2021) to within a constant factor.$$w=n^{\Omega (1)}$$ $w={n}^{\Omega \left(1\right)}$ 
We present an explicit pseudorandom generator with seed length tildeO((log n)w+1) for readonce, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length n^{1/2+o(1)}. A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w readonce, oblivious branching program B : {0, 1}^n > {0, 1}, any k in {1,2,...,n}, Sum_{S subseteq [n];S=k} \hat{B}(S) leq O(log n)^{wk}. This settles a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM'13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.more » « less

We give new upper and lower bounds on the power of several restricted classes of arbitraryorder readonce branching programs (ROBPs) and standardorder ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for spacebounded computation.  Regular SOBPs of length n and width ⌊w(n+1)/2⌋ can exactly simulate general SOBPs of length n and width w, and moreover an n/2o(n) blowup in width is necessary for such a simulation. Our result extends and simplifies prior averagecase simulations (Reingold, Trevisan, and Vadhan (STOC 2006), Bogdanov, Hoza, Prakriya, and Pyne (CCC 2022)), in particular implying that weighted pseudorandom generators (Braverman, Cohen, and Garg (SICOMP 2020)) for regular SOBPs of width poly(n) or larger automatically extend to general SOBPs. Furthermore, our simulation also extends to general (even readmany) oblivious branching programs.  There exist natural functions computable by regular SOBPs of constant width that are averagecase hard for permutation SOBPs of exponential width. Indeed, we show that InnerProduct mod 2 is averagecase hard for arbitraryorder permutation ROBPs of exponential width.  There exist functions computable by constantwidth arbitraryorder permutation ROBPs that are worstcase hard for exponentialwidth SOBPs.  Readtwice permutation branching programs of subexponential width can simulate polynomialwidth arbitraryorder ROBPs.more » « less