METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 21, 15:00-16:00 - Anup Rao (U. Washington, Seattle)
Pseudorandom generators for regular branching programs
----
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. For every width d and length n, our pseudorandom generator uses a seed of length O((log d +log log n + log(1/epsilon )) 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 epsilon.

We shall also discuss a simple argument that shows that the set of all binary strings with less than d non-zero entries forms a hitting set for regular width d branching programs.

Joint work with Mark Braverman, Ran Raz and Amir Yehudayoff.