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.
Mathematical Foundations of Computer Science 2001: Lecture Notes in Computer Science, 2001, p. 272-284
Main Research Area:
MFCS'01. 26th International Symposium on Mathematical Foundations of Computer Science., 2001