[Colloquium] [Staff] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Tue Jan 29 07:05:21 CST 2013
*REMINDER*
THEORY SEMINAR
Tuesday, January 29, 2013
3:00 p.m.
Ryerson 251
Siu-On Chan
University of California at Berkeley
www.eecs.berkeley.edu/~siuon/
Title: Approximation Resistance from Pairwise Independent Subgroups
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, bypassing the Unique-Games Conjecture for predicates with 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.
Host: Madhur Tulsiani
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130129/04fae668/attachment.htm
More information about the Colloquium
mailing list