About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
CCC 2011
Conference paper
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.