 Award ID(s):
 1749810
 NSFPAR ID:
 10079983
 Date Published:
 Journal Name:
 Proceedings of the annual ACM Symposium on Theory of Computing
 ISSN:
 07378017
 Page Range / eLocation ID:
 363375
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)We give the first pseudorandom generators with sublinear seed length for the following variants of readonce branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unboundedwidth unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [LeePyneVadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [HozaPyneVadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unboundedwidth unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no nontrivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [BogdanovHozaPrakriyaPyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε). 3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a nontrivial seed length is known for this class. We remark that there are some functions computable by constantwidth adaptive branching programs but not by subexponentialwidth unordered branching programs. In terms of techniques, we indeed show that the ForbesKelley PRG (with the right parameters) from [ForbesKelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of ForbesKelly, and we believe it further demonstrates the versatility of the ForbesKelley PRG.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

Wootters, Mary ; Sanita, Laura (Ed.)The orbit of an nvariate polynomial f(x) over a field 𝔽 is the set {f(Ax+b) ∣ A ∈ GL(n, 𝔽) and b ∈ 𝔽ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hittingsets for the orbit of readonce oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog w})} for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give a hitting set of size (ndw)^{O(min{w²,dlog w})} for the orbit of polynomials computed by wwidth ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of anyorder ROABPs) and (nw)^{O(w⁶log n)} size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance d > n, was asked as an open problem by [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting. We prove some new rank concentration results by establishing lowcone concentration for the polynomials over vector spaces, and they strengthen some previously known lowsupport based rank concentrations shown in [Michael A. Forbes et al., 2013]. These new lowcone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when lowcone rank concentration has been used for designing hitting sets.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)}$ 
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