Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Improved NP-Inapproximability for 2-Variable Linear Equations
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).ORCID iD: 0000-0002-5379-345X
Ecole Polytech Fed Lausanne, Ola Svenssons Grp, Lausanne, Switzerland..
Indian Inst Technol, Madras, Tamil Nadu, India..
Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA..
Show others and affiliations
2017 (English)In: Theory of Computing, ISSN 1557-2862, E-ISSN 1557-2862, Vol. 13, article id 19Article in journal (Refereed) Published
Abstract [en]

An instance of the 2-Lin(2) problem is a system of equations of the form "x(i)+x(j)= b (mod 2)." Given such a system in which it is possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C epsilon fraction of equations, for any C < 11/8 - 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitations on gadget reductions was known.

Place, publisher, year, edition, pages
UNIV CHICAGO, DEPT COMPUTER SCIENCE , 2017. Vol. 13, article id 19
Keywords [en]
approximability, unique games, gadget, linear programming
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-269592DOI: 10.4086/toc.2017.v013a019ISI: 000455093200009Scopus ID: 2-s2.0-85044754930OAI: oai:DiVA.org:kth-269592DiVA, id: diva2:1423194
Note

QC 20200414

Available from: 2020-04-14 Created: 2020-04-14 Last updated: 2020-04-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Mathematics (Div.)
In the same journal
Theory of Computing
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 11 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf