2026-07-23T08:19:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5311 2024-03-06T10:36:17Z ddc:004 open_access

Improved NP-Inapproximability for 2-Variable Linear Equations Håstad, Johan Huang, Sangxia Manokaran, Rajsekar O’Donnell, Ryan Wright, John approximability unique games linear equation gadget linear programming An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's 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 the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 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 limitation on gadget reductions was known. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johan Håstad and Sangxia Huang and Rajsekar Manokaran and Ryan O’Donnell and John Wright 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.341 urn:nbn:de:0030-drops-53112 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.341 eng https://creativecommons.org/licenses/by/3.0/legalcode