Shyan Akmal - MAJ-3SAT in Polynomial Time [Nov. 5, 2021]

 Summary

Orateur: Shyan Shaer Akmal
Title: Majority-3SAT (and Related Problems) in Polynomial Time
Abstract: Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^{n-1} satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k.
It recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ∈(0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^{n} satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time).
In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.

Tags: cana seminars