On pseudorandom generators in NC0

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Department of Computer Science
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.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2001 : Lecture Notes in Computer Science
EditorsJiŕı Sgall, Ales Pultr, Petr Kolman
Number of pages13
Volume2136/2001
PublisherSpringer
Publication year2001
EditionLecture Notes in Computer Science 2136
Pages272-284
ISBN (print)3-540-42496-2
ISBN (Electronic)10.1007/3-540-44683-4_24
Publication statusPublished - 2001
EventMFCS'01. 26th International Symposium on Mathematical Foundations of Computer Science. - Marianske Lazne, Czech Republic
Duration: 27 Aug 200131 Aug 2001
Conference number: 26

Conference

ConferenceMFCS'01. 26th International Symposium on Mathematical Foundations of Computer Science.
Nummer26
LandCzech Republic
ByMarianske Lazne
Periode27/08/200131/08/2001

See relations at Aarhus University Citationformats

ID: 281295