Hardness of Maximum Constraint Satisfaction
Siu On Chan
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2013-57
May 13, 2013
http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-57.pdf
Maximum constraint satisfaction problem (Max-CSP) is a rich class of combinatorial optimization problems. In this dissertation, 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 approximation resistant if its predicate contains a subgroup that is balanced pairwise independent. Our main result is related to previous works conditioned on the Unique-Games Conjecture and integrality gaps in sum-of-squares semidefinite programming hierarchies. 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.
Advisor: Elchanan Mossel
BibTeX citation:
@phdthesis{Chan:EECS-2013-57,
Author = {Chan, Siu On},
Title = {Hardness of Maximum Constraint Satisfaction},
School = {EECS Department, University of California, Berkeley},
Year = {2013},
Month = {May},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-57.html},
Number = {UCB/EECS-2013-57},
Abstract = {Maximum constraint satisfaction problem (Max-CSP) is a rich class of combinatorial optimization problems. In this dissertation, 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 approximation resistant if its predicate contains a subgroup that is balanced pairwise independent. Our main result is related to previous works conditioned on the Unique-Games Conjecture and integrality gaps in sum-of-squares semidefinite programming hierarchies.
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.}
}
EndNote citation:
%0 Thesis %A Chan, Siu On %T Hardness of Maximum Constraint Satisfaction %I EECS Department, University of California, Berkeley %D 2013 %8 May 13 %@ UCB/EECS-2013-57 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-57.html %F Chan:EECS-2013-57