Title :
Pseudorandom Generators for Read-Once ACC^0
Author :
Gavinsky, Dmitry ; Lovett, Shachar ; Srinivasan, Srikanth
Author_Institution :
NEC Labs. America, Inc., Princeton, NJ, USA
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.
Keywords :
computational complexity; logic circuits; logic gates; random number generation; explicit construction; polylogarithmic seed length; pseudorandom generators; read-once ACC0; read-once constant depth circuits; unbounded fan-in AND gate; unbounded fan-in NOT gate; unbounded fan-in OR gate; unbounded fan-in generalized modulo m gate; Computational modeling; Context; Generators; Integrated circuit modeling; Logic gates; Polynomials; Random variables; Derandomization; Pseudorandom generators; Random restrictions;
Conference_Titel :
Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on
Conference_Location :
Porto
Print_ISBN :
978-1-4673-1663-7
DOI :
10.1109/CCC.2012.37
