Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/CCC.2012.37 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
explicit construction,seed length,read-once acc,unbounded fan-in,read-once constant depth circuit,read-once circuit,pseudorandom generators,pseudorandom generator,generalized modulo m gate,logic gates,computational complexity,random variables,computational modeling,polynomials,generators,random number generation,logic circuits | Discrete mathematics,Pseudorandom generators for polynomials,Lavarand,Pseudorandomness,Random seed,Pseudorandom generator,Random number generation,Pseudorandom generator theorem,Mathematics,Pseudorandom number generator | Conference |
ISSN | Citations | PageRank |
1093-0159 | 1 | 0.38 |
References | Authors | |
10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dmitry Gavinsky | 1 | 166 | 20.21 |
Shachar Lovett | 2 | 520 | 55.02 |
Srikanth Srinivasan | 3 | 132 | 21.31 |