Pseudorandom Generators for Regular Branching Programs


June 11, 2010


Anup Rao


University of Washington


This work is about how finding efficient ways to stretch a small random string into a long string that cannot be distinguished from random by a computation with small memory. A branching program of width d and length n is a program that reads n bits in order, and uses them to transition to one of d possible states. The transition function may depend on which bit is read. 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 (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/e)) 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 e. 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 2e/?2.
This is joint work with Mark Braverman, Ran Raz and Amir Yehudayoff.


Anup Rao

Anup Rao is graduated from UT Austin and postdoc’ed at the Center for Computational Intractibility and the Institute for Advanced Study before becoming a professor at UW.