[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

The University of Chicago
Department of Computer Science & Mathematics
Combinatorics & Theoretical Seminar
 
Li-Yang Tan
University of Chicago - TTIC

Title: “Derandomized search for CNF satisfying assignments in almost polynomial time”

Abstract: 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)| \geq \eps 2^n, runs in time n^{\tilde{O}(\log\log n)^2} for \eps \ge 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^{\tilde{\Omega}(\log n)} even for constant \eps.

Joint work with Rocco Servedio.

Host: Prof. Alexander Razborov

*Refreshments will be served prior to the talk in Ryerson 255 @ 2:30 pm*

Tuesday, September 27, 2016
3:00 pm
Ryerson 251
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160926/0c3bde8f/attachment.html>