Pseudorandom generators for regular branching programs

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

Abstract

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ε)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ε. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ε/γ 2.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages40-47
Number of pages8
DOIs
StatePublished - Dec 1 2010
Externally publishedYes
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Branching programs
  • Explicit constructions
  • Pseudorandomness

Fingerprint Dive into the research topics of 'Pseudorandom generators for regular branching programs'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Rao, A., Raz, R., & Yehudayoff, A. (2010). Pseudorandom generators for regular branching programs. In Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 (pp. 40-47). [5670950] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2010.11