← All problems

10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut

Let G=(V,E)G=(V,E) be a finite undirected graph with at least one edge, let AA be its adjacency matrix, and let DGD_G be the diagonal matrix of vertex degrees. Write L=(DG−A)/4L=(D_G-A)/4. For x∈{±1}Vx\in\{\pm1\}^{V}, the quantity xTLxx^{\mathsf T}Lx is the number of edges cut by the signs of xx, so

MaxCut⁡(G)=max⁡x∈{±1}VxTLx.\operatorname{MaxCut}(G)=\max_{x\in\{\pm1\}^{V}}x^{\mathsf T}Lx.

For an even integer d≥2d\ge 2, define SOS⁡d(G)\operatorname{SOS}_d(G) as the least cc for which there is a polynomial identity

c=xTLx+∑i∈V(1−xi2)pi(x)+∑aqa(x)2,c=x^{\mathsf T}Lx+\sum_{i\in V}(1-x_i^2)p_i(x)+\sum_a q_a(x)^2,

where the pi,qap_i,q_a are real polynomials, every term (1−xi2)pi(1-x_i^2)p_i has degree at most dd, and every qa2q_a^2 has degree at most dd. The identity certifies an upper bound on the cut because 1−xi2=01-x_i^2=0 on the Boolean cube and squares are nonnegative. For d=2d=2, this relaxation is the Goemans–Williamson semidefinite program. Kunisky, Lecture Notes on Sum-of-Squares Optimization (2022)

For each fixed even dd, with the supremum taken over all finite graphs with at least one edge, define the worst-case integrality gap

Rd=sup⁡GSOS⁡d(G)MaxCut⁡(G).R_d=\sup_G\frac{\operatorname{SOS}_d(G)}{\operatorname{MaxCut}(G)}.

The question is to determine R4R_4 and the corresponding gaps for other fixed even degrees, in particular whether any fixed degree improves on R2=1/αGWR_2=1/\alpha_{\mathrm{GW}}; equivalently, whether its worst-case approximation guarantee exceeds the Goemans–Williamson guarantee αGW\alpha_{\mathrm{GW}}. Kunisky, Lecture Notes on Sum-of-Squares Optimization (2022)

Background

Max-Cut gives a particularly direct route from combinatorial optimization to semidefinite programming: its Boolean quadratic objective has a degree-2 semidefinite relaxation, the Goemans–Williamson SDP. The SOS hierarchy extends this viewpoint by optimizing over polynomial certificates of nonnegativity subject to the Boolean constraints. Its mathematical roots lie in Positivstellensatz methods; the use of semidefinite programming to search for such certificates was developed algorithmically by Parrilo and Lasserre around the turn of the century. Raising the degree strengthens the relaxation, while increasing its computational cost. Kunisky, Lecture Notes on Sum-of-Squares Optimization (2022) Mohanty, Raghavendra, and Xu, Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4 (STOC 2020)

The benchmark is a worst-case one: the Goemans–Williamson analysis gives the degree-2 SDP gap 1/αGW1/\alpha_{\mathrm{GW}}, and a sequence of graphs makes this bound tight. Under the Unique Games Conjecture, the same approximation threshold is also a hardness barrier for general algorithms. Thus, improving the fixed-degree SOS guarantee beyond this benchmark would have consequences beyond the analysis of the hierarchy itself. Kunisky, Lecture Notes on Sum-of-Squares Optimization (2022)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.