$(2+\epsilon)$-SAT is NP-hard

by Per Austrin, Venkatesan Guruswami, and Johan Hastad

Oded's comments

I only read the introduction, which seems to give an excellent account of the contents of this paper.

The cryptic title refers to a nicer articulation of the assertion that 3-SAT is NP-Hard because 3 is the smallest integer greater than 2. That is, if one considers the promise problem of distinguishing $(2g+1)$-CNF that have an assignment that satisfies at least $g$ literals in each clause from $(2g+1)$-CNF that are unsatisfied, then this problem is NP-hard.

The above promise problem has an approximation flavor if one thinks of the promise as a quantitative relaxation (on the ``strength'' of satisfiability rather than on the fraction of clauses satisfied). As such it may not be that surprising that this NP-hardness result is established by using a non-approximability result (for Label Cover) and that it implies a new non-approximability result (for ``hereditary discrepancy of matrices'').

The original abstract

See ECCC TR13-159

Back to list of Oded's choices.