Per Austrin: (2+ε)-SAT is NP-hard
Time: Mon 2014-12-08 12.10 - 13.00
Location: Room 4523, Lindstedtsvägen 5, KTH CSC
Participating: Per Austrin, KTH
Practicalities
Lunch is served at 12:00 noon (register at this doodle the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
Abstract
We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = w/2 - 1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = w/2, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-SAT.
We also generalize this to prove strong NP-hardness for discrepancy problems with small size sets.
The talk will be elementary and (almost) self-contained.
Joint work with Venkatesan Guruswami and Johan Håstad.