# Differences

This shows you the differences between two versions of the page.

 en:group:seminars:20110831 [2011/08/09 16:11]maatouk created en:group:seminars:20110831 [2016/06/23 11:26] (current) 2011/08/09 16:18 maatouk 2011/08/09 16:11 maatouk created Next revision Previous revision 2011/08/09 16:18 maatouk 2011/08/09 16:11 maatouk created Line 1: Line 1: - p + ---- 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.