pdf icon
Volume 13 (2017) Article 19 pp. 1-51
APPROX-RANDOM 2015 Special Issue
Improved NP-Inapproximability for $2$-Variable Linear Equations
Received: December 25, 2015
Revised: October 25, 2016
Published: December 24, 2017
Download article from ToC site:
[PDF (482K)] [PS (3389K)] [Source ZIP]
Keywords: approximability, unique games, gadget, linear programming
ACM Classification: F.1.3, F.2.2, G.1.6
AMS Classification: 68Q17, 68Q25

Abstract: [Plain Text Version]

$ \newcommand{\twolin}{2\textnormal{-Lin}(2)\xspace} \newcommand{\eps}{\epsilon} \newcommand{\NP}{\textsf{NP}} $

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).