CSAIL Event Calendar

APPROXIMATION RESISTANCE FROM PAIRWISE INDEPENDENT SUBGROUPS

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, bypassing the Unique-Games Conjecture for predicates with an abelian subgroup structure.
Our main ingredient is a new soundness reduction technique inspired by XOR-lemmas. Using this technique, we also improve the NP-hardness of approximating Independent-Set on bounded-degree graphs, Almost-Coloring, Two-Prover-One-Round-Game, and various other problems.

See other events that are part of Theory Colloquium 2012/2013

See other events happening in March 2013