# Algorithms & Complexity Seminar, MIT : Fall 2019

Organizers: Sitan Chen (sitanc AT mit DOT edu), Quanquan C. Liu (quanquan AT mit DOT edu), Nikhil Vyas (nikhilv AT mit DOT edu)

The Algorithms & Complexity Seminar for Fall 2019 will usually (unless otherwise stated) meet on Wednesdays 4pm-5pm in 32-G575 (Theory Lab on the 5th floor of the Stata Center). The style and format of these meetings are variable. Please feel free to contact the organizers to find out more details. To receive announcements of upcoming talks, subscribe to the mailing list by either visiting the mailman page or send an empty email to compalgsem-subscribe@lists.csail.mit.edu.

## Past Talks

• Wednesday, September 18, 2019: Or Zamir (Tel Aviv University). [32-G575 Time: 4-5pm]
Topic. Faster k-SAT Algorithms Using Biased-PPSZ.
Abstract. The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every $k>3$. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every $k\geq 3$. For $k=3$ we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from $1.308^n$ to $1.307^n$.

Joint work with Thomas Dueholm Hansen, Haim Kaplan and Uri Zwick.