Revised: October 25, 2016

Published: December 24, 2017

**Keywords:**approximability, unique games, gadget, linear programming

**Categories:**algorithms, inapproximability, lower bounds, Unique Games, gadget, linear programming, APPROX, APPROX-RANDOM 2015 special issue

**ACM Classification:**F.1.3, F.2.2, G.1.6

**AMS Classification:**68Q17, 68Q25

**Abstract:**
[Plain Text Version]

An instance of the $2-\text{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 is possible to satisfy all but an $\eps$ fraction of the equations, we show it is $\NP$-hard to satisfy all but a $C \eps$ fraction of equations, for any $C < {11}/{8} = 1.375$ (and any $0 < \eps \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 $\text{Unique-Games}$ problem, and it also holds for the special case of $\text{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).