On the NP-Hardness Approximation Curve for Max-2Lin(2)
<|reference_start|>On the NP-Hardness Approximation Curve for Max-2Lin(2): In the Max-2Lin(2) problem you are given a system of equations on the form $x_i + x_j \equiv b \pmod{2}$, and your objective is to find an assignment that satisfies as many equations as possible. Let $c \in [0.5, 1]$ denote the maximum fraction of satisfiable equations. In this paper we construct a curve $s (c)$ such that it is NP-hard to find a solution satisfying at least a fraction $s$ of equations. This curve either matches or improves all of the previously known inapproximability NP-hardness results for Max-2Lin(2). In particular, we show that if $c \geqslant 0.9232$ then $\frac{1 - s (c)}{1 - c} > 1.48969$, which improves the NP-hardness inapproximability constant for the min deletion version of Max-2Lin(2). Our work complements the work of O'Donnell and Wu that studied the same question assuming the Unique Games Conjecture.   Similar to earlier inapproximability results for Max-2Lin(2), we use a gadget reduction from the $(2^k - 1)$-ary Hadamard predicate. Previous works used $k$ ranging from $2$ to $4$. Our main result is a procedure for taking a gadget for some fixed $k$, and use it as a building block to construct better and better gadgets as $k$ tends to infinity. Our method can be used to boost the result of both smaller gadgets created by hand $(k = 3)$ or larger gadgets constructed using a computer $(k = 4)$.<|reference_end|>
@article{martinsson2024on,
    title={On the NP-Hardness Approximation Curve for Max-2Lin(2)},
    author={Bj"orn Martinsson},
    journal={arXiv preprint arXiv:2408.04832},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04832},
    primaryClass={cs.CC}
}