Siu On Chan
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2013-57
May 13, 2013
http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-57.html %F Chan:EECS-2013-57