Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups

摘要

In 1997, H{aa}stad showed $NP$-hardness of $(1-eps, 1/q + delta)$-approximating $maxthreelin(Z_q)$; however it was not until 2007 that Guruswami and Raghavendra were able to show $NP$-hardness of $(1-eps, delta)$-approximating $maxthreelin(Z)$. In 2004, Khot--Kindler--Mossel--O'Donnell showed $UG$-hardness of $(1-eps, delta)$-approximating $maxtwolin(Z_q)$ for $q = q(eps,delta)$ a sufficiently large constant; however achieving the same hardness for $maxtwolin(Z)$ was given as an open problem in Raghavendra's 2009 thesis.In this work we show that fairly simple modifications to the proofs of the $maxthreelin(Z_q)$ and $maxtwolin(Z_q)$ results yield optimal hardness results over $Z$. In fact, we show a kind of ``bicriteria'' hardness: even when there is a $(1-eps)$-good solution over $Z$, it is hard for an algorithm to find a $delta$-good solution over $Z$, $R$, or $Z_m$ for any $m geq q(eps,delta)$ of the algorithm's choosing.