<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">The University of Chicago<br class="">Department of Computer Science & Mathematics<br class="">Combinatorics & Theoretical Seminar<br class=""> <br class=""><b class="">Li-Yang Tan<br class="">University of Chicago - TTIC<br class=""></b><br class="">Title: “Derandomized search for CNF satisfying assignments in almost polynomial time”<br class=""><br class="">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.<br class=""><br class="">Joint work with Rocco Servedio.<br class=""><br class="">Host: Prof. Alexander Razborov<br class=""><br class="">*Refreshments will be served prior to the talk in Ryerson 255 @ 2:30 pm*<br class=""><br class=""><div style="text-align: center;" class=""><b class="">Tuesday, September 27, 2016</b></div><div style="text-align: center;" class=""><b class="">3:00 pm</b></div><div style="text-align: center;" class=""><b class="">Ryerson 251</b></div></body></html>