Pseudorandom Generators for Regular Branching Programs

Date

June 11, 2010

Speaker

Anup Rao

Affiliation

University of Washington

Overview

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.

Speakers

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.