Theory Lunch Seminar

Wednesday, December 7, 2016 - 12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates & Hillman Centers

Speaker:

LI-YANG TAN, Research Assistant Professor http://www.cs.columbia.edu/~liyang/

We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable poly(n)-clause CNF formula F that has ∣F-1(1)∣≥ε2n, runs in time nO~(loglogn)2 for ε≥1/\polylog(n) and outputs a satisfying assignment of F. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time nΩ~(logn) even for constant ε. Joint work with Rocco Servedio.

Event Website:

http://www.cs.cmu.edu/~theorylunch/20161207.html

For More Information, Contact:

Keywords:

Seminar Series