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

Ryan O'Donnell, Yi Wu, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011
Pages23-33
Number of pages11
DOIs
StatePublished - Aug 29 2011
Externally publishedYes
Event26th Annual IEEE Conference on Computational Complexity, CCC 2011 - San Jose, CA, United States
Duration: Jun 8 2011Jun 10 2011

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other26th Annual IEEE Conference on Computational Complexity, CCC 2011
CountryUnited States
CitySan Jose, CA
Period6/8/116/10/11

Fingerprint

Cyclic group
Hardness
NP-hardness
Integer
Bicriteria
Open Problems

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Cite this

O'Donnell, R., Wu, Y., & Zhou, Y. (2011). Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. In Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011 (pp. 23-33). [5959818] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2011.37

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

Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. 2011. p. 23-33 5959818 (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

O'Donnell, R, Wu, Y & Zhou, Y 2011, Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. in Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011., 5959818, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 23-33, 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, CA, United States, 6/8/11. https://doi.org/10.1109/CCC.2011.37
O'Donnell R, Wu Y, Zhou Y. Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. In Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. 2011. p. 23-33. 5959818. (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2011.37
O'Donnell, Ryan ; Wu, Yi ; Zhou, Yuan. / Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. 2011. pp. 23-33 (Proceedings of the Annual IEEE Conference on Computational Complexity).
@inproceedings{790165a6f3f04e789345bbe04c9ca52f,
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(ℤ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.",
author = "Ryan O'Donnell and Yi Wu and Yuan Zhou",
year = "2011",
month = "8",
day = "29",
doi = "10.1109/CCC.2011.37",
language = "English (US)",
isbn = "9780769544113",
series = "Proceedings of the Annual IEEE Conference on Computational Complexity",
pages = "23--33",
booktitle = "Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011",

}

TY - GEN

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 - 2011/8/29

Y1 - 2011/8/29

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/CCC.2011.37

DO - 10.1109/CCC.2011.37

M3 - Conference contribution

AN - SCOPUS:80051957065

SN - 9780769544113

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 23

EP - 33

BT - Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011

ER -