摘要：An instance of the 2−Lin(2)2−Lin(2) problem is a system of equations of the form “xi+xj=b(mod2)xi+xj=b(mod2).” Given such a system in which it is possible to satisfy all but an ϵϵ fraction of the equations, we show it is NPNP-hard to satisfy all but a CϵCϵ fraction of equations, for any C<11/8=1.375C<11/8=1.375 (and any 0<ϵ≤1/80<ϵ≤1/8). The previous best result, standing for over 1515 years, had 5/45/4 in place of 11/811/8. Our result provides the best known NPNP-hardness even for the Unique-GamesUnique-Games problem, and it also holds for the special case of Max-CutMax-Cut. The precise factor 11/811/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/23/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 CC greater than 2.542.54. Previously, no such limitations on gadget reductions was known.
关键词：approximability; unique games; gadget; linear programming
