Abstract

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups RYAN O'DONNELL, YI WU, and YUAN ZHOU, Carnegie Mellon University ° In 1997, Hastad showed NP-hardness of (1 - , 1/q + )-approximating Max-3Lin(Zq ); however, it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 - , )-approximating Max-3Lin(Z). In 2004, Khot­Kindler­Mossel­O'Donnell showed UG-hardness of (1 - , )-approximating Max-2Lin(Zq ) for q = q( , ) a sufficiently large constant; however, achieving the same hardness for Max-2Lin(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 Max-3Lin(Zq ) and Max-2Lin(Zq ) results yield optimal hardness results over Z. In fact, we show a kind of "bicriteria" hardness: Even when there is a (1 - )-good solution over Z, it is hard for an algorithm to find a -good solution over Z, R, or Zm for any m q( , ) of the algorithm's choosing. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems General Terms: Complexity, Hardness of Approximation Additional Key Words and Phrases: Max-2Lin, Max-3Lin, hardness