## 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, DNC

• A large class of “non-problematic” NC° generators with superlinear stretch (including all NC

• There is an NC

• Generators computed by NC° circuits where each output bit depends on at most 3 input bits (i.e, DNC

_{3}° circuits) and with stretch factor greater than 4 are not pseudorandom.• A large class of “non-problematic” NC° generators with superlinear stretch (including all NC

_{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

_{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 |

Editors | Jiří Sgall, Aleš Pultr, Petr Kolman |

Publisher | Springer Berlin Heidelberg |

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 |