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 super-polynomial 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 read-once 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 Russell Impagliazzo was supported in part by Simons Foundation, the Ellentuck Fund, the Friends of the Institute for Advanced Study, the National Science Foundation under grants DMS-0835373, CCF-121351, and CCF-0832797, and by a Simons Investigator Award. Raghu Meka was supported in part by the National Science Foundation under grants CCF-1553605 and DMS-0835373. David Zuckerman was supported in part by the National Science Foundation under grants CCF-0916160, CCF-1526952, CCF-1705028, and DMS-0835373, and by a Simons Investigator Award. Authors' addresses: R. Impagliazzo, University of California, San Diego; email: russell@cs.ucsd.edu; R. Meka, University of California, Los Angeles; email: raghum@cs.ucla.edu; D. Zuckerman, University of Texas at Austin; email: diz@cs.utexas.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. 11:2 R. Impagliazzo et al. Two of the most important general challenges for complexity are to prove constructive lower bounds for non-uniform measures of computational complexity such as circuit size, and to show that randomized algorithms have efficient deterministic simulations. The "Hardness vs. Randomness" paradigm [1, 6, 7, 21, 23, 36] shows that these questions are linked. More precisely, these results show how to use any problem that is hard for a class of circuits to create a pseudorandom generator (PRG) for the same class of circuits. This PRG can then be used to construct a relatively efficient deterministic version of any probabilistic algorithm with a corresponding complexity. This has been used to create unconditional PRGs for circuit classes with known lower bounds, such as for AC 0 , as well as for obtaining conditional results-implications between the existence of hard problems and derandomization for classes where no strong lower bounds are known. In the converse direction, it is easy to see that any PRG for a circuit class immediately gives a corresponding lower bound for the class. Somewhat more surprisingly, it has been shown that any efficient deterministic simulation of some probabilistic algorithms would yield circuit lower bounds [14, 17, 35] . This hardness vs. randomness connection is one of the most important tools in computational complexity. It formalizes the intuition that efficient algorithms for "meta-computational problems", where the input is a computational device from a certain class, is linked to our ability to prove lower bounds for that class. However, being so general comes at a quantitative price. Ideally, the stretch of a PRG (the output length as a function of the input length) equals the known lower bound. However, in the hardnessto-randomness constructions, there are a number of stages that each lose a large polynomial factor. In particular, this means that, for example, a quadratic or cubic circuit lower bound for a class does not immediately give any nontrivial PRG. For completely generic, "black-box", reductions between a hard problem and a PRG, some of these costs are inherent [5, 11, 28, 34] . In particular, this is an issue for those models where super-linear but not super-polynomial bounds are known, such as Boolean formulas. In this work, we show a general method for obtaining tight "hardness-to-randomness" results from the proofs of lower bounds, rather than as a black-box consequence of the lower bounds. In particular, our methods apply to lower-bound proofs that involve restricting some of the inputs to the circuit. Our construction goes in two stages. We start with a lower bound proved by the following kind of shrinkage argument: if we restrict a size s circuit leaving a p fraction of variables unset, the expected size of the restricted circuit is O (p Γ s). The best Γ for which this holds is known as the "shrinkage exponent" of the circuit class. The first stage of our construction is to derandomize the shrinkage argument, showing that there is a distribution with similar shrinkage properties that can be sampled with few bits. This stage of our argument is general, but not totally generic. While the same general construction and analysis ideas work in a variety of models, the details depend on the model. Then we show how to go from such a distribution on restrictions to a PRG. This part is generic, being identical for all models, and is closely related to the generator from [24] . The total number of bits r used by the generator is roughly s 1/(1+Γ) times the number of bits needed to sample from the distribution on restrictions. Every generator using r bits to fool tests of size s = s (r ) immediately gives a problem requiring size Ω(s (r )) to compute in the model. So, if our function s (r ) is close to the known lower bounds, this shows that we have essentially converted all of the "hardness" in the lower bound to "randomness". This is indeed the case for a variety of natural models of computation. For Boolean formulas over the de Morgan basis, we give a generator with s (r ) = r 3−o (1) , almost matching the known lower bound of s (n) = Ω(n 3 /(log 2 n log log n) due to Håstad ([12] with a polylogarithmic
Specifically, we highlight that even for read-2 oblivious branching programs, the best result is by Impagliazzo, Meka, and Zuckerman REF , who gave a PRG with seed length s 1/2+o (1) for size s branching program (note that the the dependence here is on s rather than on n).
Pseudorandomness from Shrinkage
JACM
Computer Science