Constraint Satisfaction Problems (CSPs) are a class of fundamental combinatorial optimization problems that have been extensively studied in the field of approximation algorithms and hardness of approximation. In a ground breaking result, Raghavendra showed that assuming Unique Games Conjecture, the best polynomial time approximation algorithm for all Max CSPs are given by a family of basic standard SDP relaxations. With Unique Games Conjecture remains as one of the most important open question in the field of Theoretical Computer Science, it is natural to ask whether hypothetically stronger SDP relaxations would be able to achieve better approximation ratio for Max CSPs and their variants.
In this work, we study the power of Lasserre/Sum-of-Squares SDP Hierarchy. First part of this work focuses on using Lasserre/Sum-of-Squares SDP Hierarchy to achieve better approximation ratio for certain CSPs with global cardinality constraints. We present a general framework to obtain Sum-of-Squares SDP relaxation, round SDP solution and analyze the rounding algorithm for CSPs with global cardinality constraints. To demonstrate the approach, we show that one could use Sum-of-Squares SDP to achieve a 0.85-approximation algorithm for Max Bisection problem, improving on the previously best known 0.70 ratio.
In the second part of this work, we study the computational power of general symmetric relaxations. Specifically, we show that Lasserre/Sum-of-Squares SDP solution achieves the best possible approximation ratio for all Max CSPs among all symmetric SDP relaxations of similar size. This result gives the first lower bounds for symmetric SDP relaxations of Max CSPs, and indicates that the Sum-of-Squares SDP is indeed the "right" SDP relaxation for this class of problems.
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).