Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:On pseudorandom generators in NC^0
Authors: Mary Cryan ; Peter Bro Miltersen
Date:Sep 2001
Publication Title:Lecture Notes in Computer Science
Publication Type:Book Chapter Publication Status:Published
Volume No:2136 Page Nos:272-284
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, NC^0_3 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^0_3 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^0_4 generator with a super-linear stretch that passes the linear dependency test as well as k-wise independence tests, for any constant k.
2007 by The University of Edinburgh. All Rights Reserved
Links To Paper
1st Link
2nd Link
Bibtex format
author = { Mary Cryan and Peter Bro Miltersen },
title = {On pseudorandom generators in NC^0},
book title = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
year = 2001,
month = {Sep},
volume = {2136},
pages = {272-284},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh