Algorithms and Logic Group

PPSZ on unique-kSAT

Seminars · Weekly Seminars
Speaker
Jian Ma
Affiliation
University of Electronic and Science Technology of China
Date
Time
– Asia/Shanghai
Venue
Main Building

Abstract

The CNF satisfiability problem is defined as follows: given a CNF formula $F$, decide if there exists truth-value assignment to variables such that the formula evaluates to true. In this talk, I will introduce a famous algorithm PPSZ that for long time is the fastest known algorithm for k-SAT, it solves the unique-3SAT problem in $O^*(1.306973^n)$ time, where $n$ is the number of variables in the input CNF-formula. This algorithm is a simple random algorithm analyzed by lower bounding the guessing probability. Currently best random or deterministic algorithms for kSAT, unique-kSAT are either PPSZ itself, its improvement or its derandomization.

Schedule

  • 10:00-12:00 (Time in Beijing)
  • 14:00-16:00 (Time in Auckland)
  • June 11, 2021 (Friday)

Online Meeting

Link: https://meeting.tencent.com/s/jSsMAf9XBBZ7

ID: 166 684 100