Majority-SAT is the problem of determining whether a boolean formula evaluates to true on more than half of its assignments. Majority-SAT is known to be PP-hard. In this talk, we will see a polynomial time algorithm for Majority-3SAT, which is the problem of determining whether a 3-CNF formula evaluates to true on more than half of its assignments. The result is surprising because most SAT-related problems remain hard when restricted to their corresponding 3-CNF variant.
This is a result of Shyan Akmal and Ryan Williams from FOCS 2021.
