Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR12-123 | 28th September 2012 23:46

Better pseudorandom generators from milder pseudorandom restrictions

TR12-123
Authors: Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan
Publication: 29th September 2012 00:15
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.