ALCOMFT-TR-02-67

Mary Cryan and Peter Bro Miltersen
On Pseudorandom generators in NC⁰
Århus. Work package 4. May 2002.

Abstract: In this paper we consider the question of whether \bf NC⁰ circuits can generate pseudorandom distributions. While we leave the general question unanswered, we show

• Generators computed by \bf NC⁰ circuits where each output bit depends on at most 3 input bits (i.e, \bf NC⁰₃ circuits) and with stretch factor greater than 4 are not pseudorandom.
• A large class of ``non-problematic'' \bf NC⁰ generators with superlinear stretch (including all \bf NC⁰₃ 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 \bf NC⁰₄ generator with a super-linear stretch that passes the linear dependency test as well as k-wise independence tests, for any constant k.

Postscript file: ALCOMFT-TR-02-67.ps.gz (178 kb).