On pseudorandom generators in NC⁰

TY - GEN

T1 - On pseudorandom generators in NC0

AU - Cryan, Mary

AU - Miltersen, Peter Bro

N1 - Conference code: 26

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

M3 - Article in proceedings

SN - 3-540-42496-2

VL - 2136/2001

SP - 272

EP - 284

BT - Mathematical Foundations of Computer Science 2001

A2 - Sgall, Jiŕı

A2 - Pultr, Ales

A2 - Kolman, Petr

PB - Springer

T2 - MFCS'01. 26th International Symposium on Mathematical Foundations of Computer Science.

Y2 - 27 August 2001 through 31 August 2001

ER -