Videos

Pseudorandom Generators for Regular Branching Programs

Presenter
March 16, 2010
Keywords:
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
We shall discuss 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, the pseudorandom generator uses a seed of length $O((log d + log log n + log(1/p)) 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 $p > 0$