Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research
– | • 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 language | English |
---|---|
Title of host publication | Mathematical Foundations of Computer Science 2001 : Lecture Notes in Computer Science |
Editors | Jiŕı Sgall, Ales Pultr, Petr Kolman |
Number of pages | 13 |
Volume | 2136/2001 |
Publisher | Springer |
Publication year | 2001 |
Edition | Lecture Notes in Computer Science 2136 |
Pages | 272-284 |
ISBN (print) | 3-540-42496-2 |
ISBN (Electronic) | 10.1007/3-540-44683-4_24 |
Publication status | Published - 2001 |
Event | MFCS'01. 26th International Symposium on Mathematical Foundations of Computer Science. - Marianske Lazne, Czech Republic Duration: 27 Aug 2001 → 31 Aug 2001 Conference number: 26 |
Conference | MFCS'01. 26th International Symposium on Mathematical Foundations of Computer Science. |
---|---|
Nummer | 26 |
Land | Czech Republic |
By | Marianske Lazne |
Periode | 27/08/2001 → 31/08/2001 |
See relations at Aarhus University Citationformats
ID: 281295