Approximability and Proof Complexity in Constraint Satisfaction Problems
Explore the realm of constraint satisfaction problems, from Max-Cut to Unique Games, delving into approximation algorithms and NP-hardness. Dive into open questions surrounding the Unique Games Conjecture, the hardness of Max-Cut approximations, and the quest to approximate the Balanced Separator problem within a constant factor.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Approximability and Proof Complexity Yuan Zhou, Ryan O Donnell Carnegie Mellon University
Constraint Satisfaction Problems Given: a set of variables: V a set of values: a set of "local constraints": E Goal: find an assignment : V -> to maximize #satisfied constraints in E -approximation algorithm: always outputs a solution of value at least *OPT
Example 1: Max-Cut Vertex set: V = {1, 2, 3, ..., n} Value set: = {0, 1} Typical local constraint: (i, j) in E wants (i) (j) Alternative description: Given G = (V, E), divide V into two parts, to maximize #edges across the cut Best approx. alg.: 0.878-approx. [GW'95] Best NP-hardness: 0.941 [Has'01, TSSW'00]
Example 2: Balanced Separator Vertex set: V = {1, 2, 3, ..., n} Value set: = {0, 1} Minimize #satisfied local constraints: (i, j) in E : (i) (j) Global constraint: n/3 |{i : (i) = 0}| 2n/3 Alternative description: given G = (V, E) divide V into two "balanced" parts, to minimize #edges across the cut
Example 2: Balanced Saperator (cont'd) Vertex set: V = {1, 2, 3, ..., n} Value set: = {0, 1} Minimize #satisfied local constraints: (i, j) in E : (i) (j) Global constraint: n/3 |{i : (i) = 0}| 2n/3 Best approx. alg.: sqrt{log n}-approx. [ARV'04] Only (1+ )-approx. alg. is ruled out assuming 3- SAT does not have subexp time alg. [AMS'07]
Example 3: Unique Games Vertex set: V = {1, 2, 3, ..., n} Value set: = {0, 1, 2, ..., q - 1} Maximize #satisfied local constraints: {(i, j), c} in E : (i) - (j) = c (mod q) Unique Games Conjecture (UGC)[Kho'02, KKMO'07] No poly-time algorithm, given an instance where optimal solution satisfies (1- ) constraints, finds a solution satisfying constraints Stronger than (implies) "no constant approx. alg."
Open questions Is UGC true? Is Max-Cut hard to approximate better than 0.878? Is Balanced Separator hard to approximate with in constant factor? Easier questions Do the known powerful optimization algorithms solve UG/Max-Cut/Balanced Separator?
SDP Relaxation hierarchies A systematic way to write tighter and tighter SDP relaxations BASIC-SDP r-round SDP relaxation in roughly time n (r ) O ? ARV SDP for Balanced Separator UG( ) GW SDP for Maxcut (0.878-approx.) Examples Sherali-Adams+SDP [SA'90] Lasserre hierarchy [Par'00, Las'01]
How many rounds of tighening suffice? Upperbounds rounds of SA+SDP suffice for UG [ABS'10, BRS'11] Lowerbounds [KV'05, DKSV'06, RS'09, BGHMRS '12] (also known as constructing integrality gap instances) rounds of SA+SDP needed for UG rounds of SA+SDP needed for better-than-0.878 approx for Max-Cut rounds for SA+SDP needed for constant approx. for Balanced Separator ) 1 ( n ) 1 ( exp((log log ) ) n ) 1 ( exp((log log ) ) n ) 1 ( (log log ) n
From SA+SDP to Lasserre SDP Are the integrality gap instances for SA+SDP also hard for Lasserre SDP? Previous result [BBHKSZ'12] No for UG 8-round Lasserre solves the Unique Games lowerbound instances
From SA+SDP to Lasserre SDP (contd) Are the integrality gap instances for SA+SDP also hard for Lasserre SDP? This paper No for Max-Cut and Balanced Separator Constant-round Lasserre gives better-than- 0.878 approximation for Max-Cut lowerbound instances 4-round Lasserre gives constant approximation for the the Balanced Separator lowerbound instances
Proof overview Integrality gap instance SDP completeness: good vector solution Integral soundness: no good integral solution Show the instance is not integrality gap instance for Lasserre SDP no good vector solution we bound the value of the dual of the SDP interpret the dual as a proof system ( SOSd/sum-of-squares proof system") lift the soundness proof to the proof system
What is the SOSd proof system?
Polynomial optimization Maximize/Minimize Subject to q r (x ) p = = = ( ( ) ) , 0 , 0 ( x ) , 0 , 0 ( x ) 0 x x q r x ) q x ) 1 2 ( m ( ' 0 r 1 2 m all functions are low-degree n-variate polynomials Max-Cut example: Maximize x 2) E x ( x i j (i,j) E = 1 ( ) , 0 x i s.t. i i
Polynomial optimization (cont'd) Maximize/Minimize Subject to q r (x ) p = = = ( ( ) ) , 0 , 0 ( x ) , 0 , 0 ( x ) 0 x x q r x ) q x ) 1 2 ( m ( ' 0 r 1 2 m all functions are low-degree n-variate polynomials Balanced Separator example: Minimize x x 2) E ( x i j (i,j) E = 1 ( i x ) , 0 x i s.t. i E i [ ] , E i [ ] x 1 2 3 3 i i
Certifying no good solution Maximize Subject to (x ) p = = = ( ( ) ) , 0 , 0 ( x ) , 0 , 0 ( x ) 0 q r x x q r x ) q x ) 1 2 ( m ( ' 0 r 1 2 m To certify that there is no solution better than , simply say that the following equalities & inequalities are infeasible ) (x p , 0 ) ( , 0 ) ( 2 1 = = x q x q , 0 ) ( , 0 ) ( 2 1 x r x r = ( x ) 0 q x ) m ( ' 0 r m
The Sum-of-Squares proof system To show the following equalities & inequalities are infeasible, ) ( , 0 ) ( 2 1 = = x q x q ) ( , 0 ) ( 2 1 x r x r = , 0 , 0 ( x ) 0 q x ) m ( ' 0 r m = Show that = + 1 ( ) ( ) ( ) f x q x h x i i 1 ... i m where is a sum of squared polynomials, including 's A degree-d "Sum-of-Squares" refutation, where ) {deg( max f d i i (x ) ri h (x ) = + deg( ), deg( )} q h i
Positivstellensatz Subject to some mild technical conditions, every infeasible system has such a refutation Caveat: fi s and h might need to have high degree. Lasserre SDP and SOSd proof system A degree-d SOS refutation O(d)-round Lasserre SDP is infeasible
Summary Defined the degree-d SOS proof system Remaining task Integral soundness proof low-degree refutation in the SOS proof system
Example 1 To refute 2 x 1 ( x ) 0 x We simply write = + ) 2 + 2) 1 1 1 ( x ) ( ( x x x A degree-2 SOS refutation
One-slide How-to Thm: Max-Cut of this graph is blah Proof: Invariance Principle Majority-Is-Stablest Check out these polynomials. Thm: Min-Balanced-Separator in this graph is blah Proof: hypercontractivity Check out these polynomials.
Example 2: Max-Cut on triangle graph To refute + + + 2 2 2 ( ) ( ) ( ) 2 x x x x x x 1 2 2 3 3 1 = = = 1 ( 1 x ) , 0 1 ( 2 x ) , 0 1 ( 3 x ) 0 x x x 1 2 3 We "simply" write ... ...
Example 2: Max-Cut on triangle graph (cont'd) ( ( ) = + + 2 2 2 ( ) ( ) ( ) 2 x x x x x x 1 x 2 x 2 3 3 1 + + + + ) 1 + + ) 1 2 2 2 ) ( ( x x x x x x x x x 1 2 2 3 1 3 2 1 2 2 3 + + + 2 2 2 3 1 ( 1 x )( 2 ) 1 x x x x x x 1 2 3 + + ) 3 + 2 3 1 ( 2 )( 2 2 2 x x x x x x x 2 1 1 3 1 3 + + ) 1 + 1 ( 3 x )( 2 x x x x x 3 1 2 1 2 A degree-4 SoS refutation
Latest results Our theorem on Max-Cut is improved by [DMN 12] Constant-round Lasserre SDP almost exactly solves the known instances Constant-round Lasserre SDP solves the hard instances for Vertex-Cover [KOTZ 12] Open question Does constant-round Lasserre SDP solve the known instances for all the CSPs? I.e. SOS-ize Raghavendra s theorem.
