
Speaker Anup Rao Host David Wilson Affiliation University of Washington Duration 00:56:33 Date recorded 11 June 2010 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 readonce branching programs of small width. A branching program is regular if the indegree 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 readonce branching program, except with probability e. We also give a result for general readonce 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 2e/?^{2}. This is joint work with Mark Braverman, Ran Raz and Amir Yehudayoff.
©2010 Microsoft Corporation. All rights reserved.
