Date: 2003.12.17, 13:00-14:00
Place: CELC Seminar Room, Tokyo Tech. Tamachi 4F
http://www.al.ics.saitama-u.ac.jp/elc/en/celc/

Title: Approximation Resistance from Pairwise Independent Subgroups
by: Siu-On Chan (MSR New England) 

Abstract:
We show optimal (up to a constant factor) NP-hardness for maximum
constraint satisfaction problem with k variables per constraint
(Max-k-CSP), whenever k is larger than the domain size. This follows
from our main result concerning CSPs given by a predicate: a CSP is
approximationresistant 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.

Our main ingredient is a new gap-amplification 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.