ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-110 | 4th September 2012 18:23

Approximation Resistance from Pairwise Independent Subgroups

RSS-Feed




TR12-110
Authors: Siu On Chan
Publication: 5th September 2012 11:08
Downloads: 2500
Keywords: 


Abstract:

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain,
whenever k is larger than the domain size. This follows from our main result concerning predicates
over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that
is balanced pairwise independent. This gives an unconditional analogue of Austrin–Mossel hardness
result, taking away their Unique-Games Conjecture assumption in exchange for an abelian subgroup
structure.
Our main ingredient is a new technique to reduce soundness, which is inspired by XOR-lemmas.
Using this technique, we also improve the NP-hardness of approximating Independent-Set on bounded
degree graphs, Almost-Coloring, and Two-Prover-One-Round-Game.



ISSN 1433-8092 | Imprint