One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer from a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don’t know superpolynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs which are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Γ if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of p Γ + o (1) . Our PRG uses a seed of length s 1/(Γ + 1) + o (1) to fool circuits in the family of size s . By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: (1) For de Morgan formulas, seed length s 1/3+ o (1) ; (2) For formulas over an arbitrary basis, seed length s 1/2+ o (1) ; (3) For readonce de Morgan formulas, seed length s .234... ; (4) For branching programs of size s , seed length s 1/2+ o (1) . The previous best PRGs known for these classes used seeds of length bigger than n /2 to output n bits, and worked only for size s = O ( n ) [8].
more »
« less
Fooling ConstantDepth Threshold Circuits (Extended Abstract)
We present new constructions of pseudorandom generators (PRGs) for two of the most widely studied nonuniform circuit classes in complexity theory. Our main result is a construction of the first nontrivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and superlinear size. This PRG fools circuits with depth d∈N and n1+δ wires, where δ=2−O(d) , using seed length O(n1−δ) and with error 2−nδ . This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuitanalysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds. Our second contribution is a PRG for De Morgan formulas of size s whose seed length is s1/3+o(1)⋅polylog(1/ϵ) for error ϵ . In particular, our PRG can fool formulas of subcubic size s=n3−Ω(1) with an exponentially small error ϵ=exp(−nΩ(1)) . This significantly improves the inversepolynomial error of the previous stateoftheart for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currentlyknown lower bounds for this class. In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a nonnatural “hybrid computational model” that combines several computational models.
more »
« less
 Award ID(s):
 1947546
 NSFPAR ID:
 10384268
 Date Published:
 Journal Name:
 Annual Symposium on Foundations of Computer Science
 Page Range / eLocation ID:
 104 to 115
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer from a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don't know superpolynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs that are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Gamma if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of p^{Gamma + o(1)}. Our PRG uses a seed of length s^{1/(Gamma + 1) + o(1)} to fool circuits in the family of size s. By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: 1. For de Morgan formulas, seed length s^{1/3+o(1)}; 2. For formulas over an arbitrary basis, seed length s^{1/2+o(1)}; 3. For readonce de Morgan formulas, seed length s^{.234...}; 4. For branching programs of size s, seed length s^{1/2+o(1)}. The previous best PRGs known for these classes used seeds of length bigger than n/2 to output n bits, and worked only when the size s=O(n).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

The ExponentialTime Hypothesis ( \(\mathtt {ETH} \) ) is a strengthening of the \(\mathcal {P} \ne \mathcal {NP} \) conjecture, stating that \(3\text{}\mathtt {SAT} \) on n variables cannot be solved in (uniform) time 2 ϵ · n , for some ϵ > 0. In recent years, analogous hypotheses that are “exponentiallystrong” forms of other classical complexity conjectures (such as \(\mathcal {NP}\nsubseteq \mathcal {BPP} \) or \(co\mathcal {NP}\nsubseteq \mathcal {NP} \) ) have also been introduced, and have become widely influential. In this work, we focus on the interaction of exponentialtime hypotheses with the fundamental and closelyrelated questions of derandomization and circuit lower bounds . We show that even relativelymild variants of exponentialtime hypotheses have farreaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: (1) The Randomized ExponentialTime Hypothesis ( \(\mathsf {rETH} \) ) implies that \(\mathcal {BPP} \) can be simulated on “averagecase” in deterministic (nearly)polynomialtime (i.e., in time \(2^{\tilde{O}(\log (n))}=n^{\mathrm{loglog}(n)^{O(1)}} \) ). The derandomization relies on a conditional construction of a pseudorandom generator with nearexponential stretch (i.e., with seed length \(\tilde{O}(\log (n)) \) ); this significantly improves the stateoftheart in uniform “hardnesstorandomness” results, which previously only yielded pseudorandom generators with subexponential stretch from such hypotheses. (2) The NonDeterministic ExponentialTime Hypothesis ( \(\mathsf {NETH} \) ) implies that derandomization of \(\mathcal {BPP} \) is completely equivalent to circuit lower bounds against \(\mathcal {E} \) , and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of \(\mathsf {NETH} \) , and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Lastly, we show that disproving certain exponentialtime hypotheses requires proving breakthrough circuit lower bounds. In particular, if \(\mathtt {CircuitSAT} \) for circuits over n bits of size poly( n ) can be solved by probabilistic algorithms in time 2 n /polylog( n ) , then \(\mathcal {BPE} \) does not have circuits of quasilinear size.more » « less

Abstract We show that a very simple pseudorandom generator fools intersections of k linear threshold functions (LTFs) and arbitrary functions of k LTFs over ndimensional Gaussian space. The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of PRGs for functions of halfspaces. Our analysis for arbitrary functions of LTFs establishes bounds on the Wasserstein distance between Gaussian random vectors with similar covariance matrices, and combines these bounds with a conversion from Wasserstein distance to "unionoforthants" distance from [Xi Chen et al., 2014]. Our analysis for intersections of LTFs uses extensions of the classical SudakovFernique type inequalities, which give bounds on the difference between the expectations of the maxima of two Gaussian random vectors with similar covariance matrices. For all values of k, our generator has seed length O(log n) + poly(k) for arbitrary functions of k LTFs and O(log n) + poly(log k) for intersections of k LTFs. The best previous result, due to [Gopalan et al., 2010], only gave such PRGs for arbitrary functions of k LTFs when k=O(log log n) and for intersections of k LTFs when k=O((log n)/(log log n)). Thus our PRG achieves an O(log n) seed length for values of k that are exponentially larger than previous work could achieve. By combining our PRG over Gaussian space with an invariance principle for arbitrary functions of LTFs and with a regularity lemma, we obtain a deterministic algorithm that approximately counts satisfying assignments of arbitrary functions of k general LTFs over {0,1}^n in time poly(n) * 2^{poly(k,1/epsilon)} for all values of k. This algorithm has a poly(n) runtime for k =(log n)^c for some absolute constant c>0, while the previous best poly(n)time algorithms could only handle k = O(log log n). For intersections of LTFs, by combining these tools with a recent PRG due to [R. O'Donnell et al., 2018], we obtain a deterministic algorithm that can approximately count satisfying assignments of intersections of k general LTFs over {0,1}^n in time poly(n) * 2^{poly(log k, 1/epsilon)}. This algorithm has a poly(n) runtime for k =2^{(log n)^c} for some absolute constant c>0, while the previous best poly(n)time algorithms for intersections of k LTFs, due to [Gopalan et al., 2010], could only handle k=O((log n)/(log log n)).more » « less