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

Ryan O'Donnell, Yi Wu, Yuan Zhou

Research output: Contribution to journalArticle

Abstract

In 1997, Håstad 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.

Original languageEnglish (US)
Article number9
JournalACM Transactions on Computation Theory
Volume7
Issue number2
DOIs
StatePublished - May 1 2015
Externally publishedYes

Fingerprint

Cyclic group
Hardness
NP-hardness
Integer
Bicriteria
Open Problems

Keywords

  • Hardness of approximation
  • Large alphabet sets
  • Max-2Lin
  • Max-3Lin
  • The unique games conjecture

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Cite this

Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. / O'Donnell, Ryan; Wu, Yi; Zhou, Yuan.

In: ACM Transactions on Computation Theory, Vol. 7, No. 2, 9, 01.05.2015.

Research output: Contribution to journalArticle

@article{2b1332047f724f829d13e55bb3a6ee16,
title = "Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups",
abstract = "In 1997, H{\aa}stad 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.",
keywords = "Hardness of approximation, Large alphabet sets, Max-2Lin, Max-3Lin, The unique games conjecture",
author = "Ryan O'Donnell and Yi Wu and Yuan Zhou",
year = "2015",
month = "5",
day = "1",
doi = "10.1145/2751322",
language = "English (US)",
volume = "7",
journal = "ACM Transactions on Computation Theory",
issn = "1942-3454",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

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

AU - O'Donnell, Ryan

AU - Wu, Yi

AU - Zhou, Yuan

PY - 2015/5/1

Y1 - 2015/5/1

N2 - In 1997, Håstad 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.

AB - In 1997, Håstad 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.

KW - Hardness of approximation

KW - Large alphabet sets

KW - Max-2Lin

KW - Max-3Lin

KW - The unique games conjecture

UR - http://www.scopus.com/inward/record.url?scp=84930168274&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84930168274&partnerID=8YFLogxK

U2 - 10.1145/2751322

DO - 10.1145/2751322

M3 - Article

AN - SCOPUS:84930168274

VL - 7

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

SN - 1942-3454

IS - 2

M1 - 9

ER -