Abstract / Description of output
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.
• 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 language | English |
---|---|
Title of host publication | Mathematical Foundations of Computer Science 2001 |
Editors | Jiří Sgall, Aleš Pultr, Petr Kolman |
Publisher | Springer |
Pages | 272-284 |
Number of pages | 13 |
Volume | 2136 |
ISBN (Electronic) | 978-3-540-44683-5 |
ISBN (Print) | 978-3-540-42496-3 |
DOIs | |
Publication status | Published - 2001 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Berlin Heidelberg |
Volume | 2136 |