10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
Let be a finite undirected graph with at least one edge, let be its adjacency matrix, and let be the diagonal matrix of vertex degrees. Write . For , the quantity is the number of edges cut by the signs of , so
For an even integer , define as the least for which there is a polynomial identity
where the are real polynomials, every term has degree at most , and every has degree at most . The identity certifies an upper bound on the cut because on the Boolean cube and squares are nonnegative. For , this relaxation is the Goemans–Williamson semidefinite program. Kunisky, Lecture Notes on Sum-of-Squares Optimization (2022)
For each fixed even , with the supremum taken over all finite graphs with at least one edge, define the worst-case integrality gap
The question is to determine and the corresponding gaps for other fixed even degrees, in particular whether any fixed degree improves on ; equivalently, whether its worst-case approximation guarantee exceeds the Goemans–Williamson guarantee . 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 , 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)
Progress summary
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.