Per Austrin: (2+ε)-SAT is NP-hard

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.