## $(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.