Volume 13 (2017) Article 19 pp. 1-51
APPROX-RANDOM 2015 Special Issue

Improved NP-Inapproximability for $2$-Variable Linear Equations

by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright

Received: December 25, 2015
Revised: October 25, 2016
Published: December 24, 2017

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

DOI: 10.4086/toc.2017.v013a019

© 2017 Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright
Licensed under a Creative Commons Attribution License (CC-BY)