Pseudorandom generators for regular branching programs

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

Research output: Contribution to journalArticle

15 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, except for the first layer. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + loglogn + 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 nonregular) 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. Finally, we show that the set of all binary strings with less than d nonzero entries forms a hitting set for regular width d branching programs.

Original languageEnglish (US)
Pages (from-to)973-986
Number of pages14
JournalSIAM Journal on Computing
Volume43
Issue number3
DOIs
StatePublished - Jan 1 2014

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

Cite this