Tata Institute of Fundamental Research
Majority-3SAT in Polynomial Time
STCS Seminar
Speaker:
Ratnakar Medepalli
Organiser:
Ramprasad Saptharishi
Date:
Friday, 14 Jul 2023, 14:00 to 15:00
Venue:
A201
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Ratnakar Medepalli |
| Organiser: | Ramprasad Saptharishi |
| Date: | Friday, 14 Jul 2023, 14:00 to 15:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
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.
This is a result of Shyan Akmal and Ryan Williams from FOCS 2021.