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.

Advisors: 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