| Computer Science/Discrete Mathematics Seminar II | |
| Topic: | Pseudorandom Generators for Read-Once ACC^0 |
| Speaker: | Srikanth Srinivasan |
| Affiliation: | DIMACS |
| Date: | Tuesday, April 24 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
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 constant depth circuits with unbounded fan-in AND, OR, NOT and generalized modulo 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 Labs) and Shachar Lovett (IAS).