|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Better Pseudorandom Generators from Milder Pseudorandom Restrictions|
|Affiliation:||Microsoft Research Silicon Valley, Mountain View, CA|
|Date:||Tuesday, April 3|
|Time/Room:||10:30am - 12:30pm/S-101|
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 that achieve near-optimal seed-length even in the low error regime. 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. Based on joint work with Raghu Meka, Omer Reingold, Luca Trevisan and Salil Vadhan.