Approximation Resistance from Pairwise-Independent Subgroups
Publication in refereed journal


Times Cited
Web of Science19WOS source URL (as at 11/01/2021) Click here for the latest count
Altmetrics Information
.

Other information
AbstractWe show optimal (up to a constant factor) NP-hardness for a maximum constraint satisfaction problem with k variables per constraint (Max-kCSP) whenever k is larger than the domain size. This follows from our main result concerning CSPs given by a predicate: A CSP is approximation resistant if its predicate contains a subgroup that is balanced pairwise independent. Our main result is analogous to Austrin and Mossel's, bypassing their Unique-Games Conjecture assumption whenever the predicate is an abelian subgroup.
All Author(s) ListChan SO
Journal nameJournal- ACM,Journal- ACM
Year2016
Month9
Day1
Volume Number63
Issue Number3
PublisherASSOC COMPUTING MACHINERY
ISSN0004-5411
eISSN1557-735X
LanguagesEnglish-United Kingdom
KeywordsInapproximability; integrality gaps; maximum constraint satisfaction problems; probabilistically checkable proofs; Theory
Web of Science Subject CategoriesComputer Science; Computer Science, Hardware & Architecture; Computer Science, Information Systems; Computer Science, Software Engineering; Computer Science, Theory & Methods

Last updated on 2021-12-01 at 00:54