PIMS - SFU Theory Seminar: Uri Zwick

  • Date: 09/30/2019
  • Time: 11:30
Lecturer(s):
Uri Zwick, Tel Aviv University
Location: 

Simon Fraser University

Topic: 

Faster k-SAT algorithms using biased-PPSZ

Description: 

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 Or Zamir.

Other Information: 

SFU TASC 1 9204