Theory of Computing
-------------------
Title     : Improved NP-Inapproximability for $2$-Variable Linear Equations
Authors   : Johan Haastad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright
Volume    : 13
Number    : 19
Pages     : 1-51
URL       : https://theoryofcomputing.org/articles/v013a019

Abstract
--------

An instance of the 2-Lin problem is a system of equations of the
form  "x_i + x_j = b mod 2."  Given such a system in which it is
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
equations, for any  C < 11/8 = 1.375  (and any  0 < \epsilon \leq 1/8).
The previous best result, standing for over 15 years, had
5/4 in place of  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  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  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 limitations on gadget reductions was known.


A preliminary version of this paper appeared in the
Proceedings of the 18th International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems
(APPROX 2015).