1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 unknown3 Department of Computer Science, Science and Technology, Aarhus University4 Department of Computer Science, Science and Technology, Aarhus University
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