Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-123 | 28th September 2012 23:46

Better pseudorandom generators from milder pseudorandom restrictions

RSS-Feed




TR12-123
Authors: Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan
Publication: 29th September 2012 00:15
Downloads: 4055
Keywords: 


Abstract:

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 CNFs 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^2 n)$ were known for these classes with polynomially small error.

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.



ISSN 1433-8092 | Imprint