- Abstract:
- In this paper we consider the question of whether NC^0 circuits can generate pseudorandom distributions. While we leave the general question unanswered, we show: - Generators computed by NC^0 circuits where each output bit depends on at most 3 input bits (i.e, NC^0_3 circuits) and with stretch factor greater than 4 are not pseudorandom. - A large class of "non-problematic"' NC^0 generators with superlinear stretch (including all NC^0_3 generators with superlinear stretch) are broken by a statistical test based on a linear dependency test combined with a pairwise independence test. - There is an NC^0_4 generator with a super-linear stretch that passes the linear dependency test as well as k-wise independence tests, for any constant k.
- Copyright:
- 2007 by The University of Edinburgh. All Rights Reserved
- Links To Paper
- 1st Link
- 2nd Link
- Bibtex format
- @InBook{EDI-INF-RR-1091,
- author = {
Mary Cryan
and Peter Bro Miltersen
},
- title = {On pseudorandom generators in NC^0},
- book title = {Lecture Notes in Computer Science},
- publisher = {Springer-Verlag},
- year = 2001,
- month = {Sep},
- volume = {2136},
- pages = {272-284},
- url = {http://www.springerlink.com/index/JWA9QRHQ8YTJEAVE.pdf},
- }
|
