Speaker: Per Austrin, KTH Royal Institute of Technology, Stockholm
Title: (2+eps)-SAT is NP-hard
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 prove that given a (2k+1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k+1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy.
(Joint work with Venkatesan Guruswami and Johan Håstad)