Speaker:

Jian Ma (University of Electronic and Science Technology of China)

Time:

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

VooVmeeting:

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

ID: 166 684 100

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.