An instance of the 2-Lin(2) problem is a system of equations of the form "\(x_i + x_j = b \pmod{2}\)". Given such a system in which it's possible to satisfy all but an \(\epsilon\) fraction of the equations, we show it is NP-hard to satisfy all but a \(C \epsilon\) fraction of the equations, for any \(C < \frac{11}{8} = 1.375\) (and any \(0 < \epsilon \leq \frac{1}{8}\)). The previous best result, standing for over 15 years, had \(\frac{5}{4}\) in place of \(\frac{11}{8}\). Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor \(\frac{11}{8}\) is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of \(\frac{3}{2}\).
Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor \(C\) greater than \(2.54\). Previously, no such limitation on gadget reductions was known.
[PDF]