Revised: October 25, 2016
Published: December 24, 2017
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).
Licensed under a Creative Commons Attribution License (CC-BY)