EPFL

Algo+LMA

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

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