Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Faster k-SAT Algorithms using biased-PPSZ
event speaker icon
Or Zamir (Tel-Aviv University)
event date icon
Wednesday, 04.12.2019, 12:30
event location icon
Taub 201 Taub Bld.
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≥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)