Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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