Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
The PPSZ algorithm by Paturi, Pudl\'ak, Saks, and Zane  is the fastest known algorithm for Unique k-SAT, where the input formula does not have more than one satisfying assignment. For k>=5 the same bounds hold for general k-SAT. We show that this is also the case for k=3,4, using a slightly modified PPSZ algorithm. We do the analysis by defining a cost for satisfiable CNF formulas, which we prove to decrease in each PPSZ step by a certain amount. This improves our previous best bounds with Moser and Scheder  for 3-SAT to O(1.308^n) and for 4-SAT to O(1.469^n).
Questions and AnswersYou need to be logged in to be able to post here.