@conference {634253,
	title = {Better pseudorandom generators via milder pseudorandom restrictions},
	booktitle = {Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS {\textquoteleft}12)},
	year = {2012},
	pages = {120-129},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {
	Version History:\&nbsp;Full version posted as ECCC TR12-123 and as\&nbsp;arXiv:1210.0049 [cs.CC].



	We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once \(\mathsf{CNF}\)s and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length \(\tilde{O}(\log(n/\epsilon))\) for error \(\epsilon\). Previously, only constructions with seed-length \(O(log^{3/2}n)\) or \(O(log^2n)\)were known for these classes with error \(\epsilon = 1/\mathrm{poly}(n)\). The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces.

},
	url = {https://ieeexplore.ieee.org/abstract/document/6375289},
	author = {Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Tevisan and Salil Vadhan}
}
