On Pseudorandom Generators in NCº

Mary Cryan, PeterBro Miltersen

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper we consider the question of whether NC° circuits can generate pseudorandom distributions. While we leave the general question unanswered, we show
• Generators computed by NC° circuits where each output bit depends on at most 3 input bits (i.e, DNC3° circuits) and with stretch factor greater than 4 are not pseudorandom.
• A large class of “non-problematic” NC° generators with superlinear stretch (including all NC3° 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 NC40 generator with a super-linear stretch that passes the linear dependency test as well as k-wise independence tests, for any constant k.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2001
EditorsJiří Sgall, Aleš Pultr, Petr Kolman
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Electronic)978-3-540-44683-5
ISBN (Print)978-3-540-42496-3
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg


Dive into the research topics of 'On Pseudorandom Generators in NCº'. Together they form a unique fingerprint.

Cite this