Change search
ReferencesLink to record
Permanent link

Direct link
Improved NP-inapproximability for 2-variable linear equations
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-1600-5290
Show others and affiliations
2015 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH , 2015, Vol. 40, 341-360 p.Conference paper (Refereed)Text
Abstract [en]

An instance of the 2-Lin(2) problem is a system of equations of the form "xi + xj = b (mod 2)". Given such a system in which it’s possible to satisfy all but an C ε fraction of the equations, we show it is NP-hard to satisfy all but a Cε fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < ε ≤ 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 limitation on gadget reductions was known.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH , 2015. Vol. 40, 341-360 p.
National Category
Mathematical Analysis
Identifiers
URN: urn:nbn:se:kth:diva-187142DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.341ScopusID: 2-s2.0-84958547344OAI: oai:DiVA.org:kth-187142DiVA: diva2:929016
Conference
18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015; Princeton UniversityPrinceton; United States
Note

QC 20160517

Available from: 2016-05-17 Created: 2016-05-17 Last updated: 2016-05-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, JohanHuang, Sangxia
By organisation
Theoretical Computer Science, TCS
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 7 hits
ReferencesLink to record
Permanent link

Direct link