Seminar: April 10

Pseudorandom Generators for Read-Once ACC^0

We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once $ACC^0$ circuits: constant depth circuits with unbounded fan-in AND, OR, NOT and generalized $MOD_m$ gates, where m is an arbitrary fixed constant. The seed length of our generator is poly-logarithmic in the number of variables and the error.

Joint work with Dmitry Gavinsky (NEC Laboratories America, Inc.) and Shachar Lovett (Institute of Advanced Study).