 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

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

null (Ed.)The GilbertVarshamov bound (nonconstructively) establishes the existence of binary codes of distance 1/2ε and rate Ω(ε 2 ) (where an upper bound of O(ε 2 log(1/ε)) is known). TaShma [STOC 2017] gave an explicit construction of εbalanced binary codes, where any two distinct codewords are at a distance between 1/2ε/2 and 1/2+ε/2, achieving a near optimal rate of Ω(ε 2+β ), where β→ 0 as ε→ 0. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by TaShma, in the adversarial error model. We prove the following results for εbalanced codes with block length N and rate Ω(ε 2+β ) in this family: For all , there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time N Oε,β(1) . For any fixed constant β independent of ε, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time (log(1/ε)) O(1) ·N Oβ(1) . For any , there are explicit εbalanced codes with rate Ω(ε 2+β ) which can be list decoded up to error 1/2ε ' in time N Oε,ε' ,β(1), where ε ' ,β→ 0 as ε→ 0. The starting point of our algorithms is the framework for list decoding directsum codes develop in Alev et al. [SODA 2020], which uses the SumofSquares SDP hierarchy. The rates obtained there were quasipolynomial in ε. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of TaShma's construction.more » « less