Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups

Abstract

In 1997, Håstad showed NP-hardness of (1 - ε,1/q + δ)-approximating Max-3Lin(ℤq); however it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 - ε,δ)-approximating Max-3Lin(ℤ). In 2004, Khot-Kindler-Mossel- O'Donnell showed UG-hardness of (1 - ε,δ)-approximating Max-2Lin(ℤq) for q = q(ε,δ) a sufficiently large constant; however achieving the same hardness for Max-2Lin(ℤ) 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 Max-3Lin(ℤq) and Max-2Lin(ℤq) results yield optimal hardness results over ℤ. In fact, we show a kind of "bicriteria" hardness: even when there is a (1 - ε)-good solution over ℤ, it is hard for an algorithm to find a δ-good solution over ℤ, ℤ, or ℤm for any m ≥ q(ε, δ) of the algorithm's choosing. © 2011 IEEE.