---- dataentry seminar ----
date_dt : 2011-08-31
title : Pseudorandomness for DNF formulas
speaker : Dr. Omid Etesami
affiliation : ALGO - EPFL
time : 16h15
room : BC 129
table : seminars
===================
template:datatemplates:seminar
-----------------------


==== abstract ====
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.