On Pseudorandom Generators in NCº

Mary Cryan, PeterBro Miltersen

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

Abstract

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
Pages272-284
Number of pages13
Volume2136
ISBN (Electronic)978-3-540-44683-5
ISBN (Print)978-3-540-42496-3
DOIs
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume2136

Fingerprint

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

Cite this