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