Differences

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

Link to this comparison view

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