Published on IAS School of Mathematics (https://www.math.ias.edu)

Home > abstract

abstract

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Pseudorandom Generators for Regular Branching Programs
Speaker:Amir Yehudayoff
Affiliation:Member, School of Mathematics
Date:Tuesday, March 16
Time/Room:10:30am - 12:30pm/West Bldg. Lecture Hall
Video Link:https://video.ias.edu/csdm/prgenregbrprgs
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. Joint work with M. Braverman, A. Rao and R. Raz.