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, DNC
3
0
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
3
0
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
4
0
generator with a super-linear stretch that passes the linear dependency test as well as k-wise independence tests, for any constant k.
|
Full version at http://www.brics.dk/~maryc/publ/psu.ps. Partially supported by the IST Programme of the EU, contract number IST-1999-14186 (ALCOM-FT).