Title

A pseudorandom generator takes a short binary string called the seed as input and generates a longer pseudorandom binary string. This talk is concerned with minimizing the seed-length while the output of the generator remains pseudorandom to DNF (Disjunctive normal form)/CNF (Conjunctive normal form) formulas, i.e. these formulas cannot distinguish the output of the generator from a truly random string. This problem is a natural problem before the more ambitious goal of derandomization of all randomized algorithms.

I will describe how to obtain the best known seed-lengths using bit strings having a pseudorandom probability distribution called “epsilon-bias distributions”. This work is built on previous work by Bazzi and Razborov. If time permits, I may also describe some optimal seed-lengths for a special class of DNF formulas, called read-once, and also the work on the so-called read-k formulas by Klivans, Lee, Wan.

If time permits, I shall also describe the limits of using epsilon-bias distributions for pseudorandomness for DNF formulas, showing that some of our results make an almost tight use. I will also talk about the circuit lower bound implications of these pseudorandom generators.

Joint work with Anindya De, Luca Trevisan, Madhur Tulsiani.