# Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?

I use the same notation as I used in this previous question, About showing algorithmic gap instance for the Goemans-Williamson SDP The same definition continue.

Given a $f : \{0,1\}^n \rightarrow \mathbb{R}$ one defines a quantity called $\overline{sos}_d(f)$ which is the smallest $c \in \mathbb{R}$ such that one can find functions on the Boolean hypercube $g_1,g_2,..,g_t : \{0,1\}^n \rightarrow \mathbb{R}$ for some $t$ with $deg(g_i) \leq d/2$ such that on the Boolean hypercube we have the equality, $c -f = \sum_{i=1}^{t} g_i ^2$

So one would say that $\overline{sos}_d(f)$ is the minimum $c$ such that the inequality $c-f \geq 0$ has a degree-d SOS certificate" on the Boolean hypercube.

Now one claims that the GW algorithm for Max-Cut is "based on the upperbound $\overline{sos}_2(f)$" and this in equation means that for the objective function of Max-Cut $f_{Max-Cut(G)} = \sum_{(i,j) \in E(G) } (x_i -x_j)^2$ we have,

$max(f_{Max-Cut(G)}) \geq \alpha_{GW} \overline{sos}_2(f_{Max-Cut(G)})$

• Is the above some immediate consequence of the GW analysis? Can someone kindly help recast that as this inequality if this is indeed true?

• Or if this inequality requires a separate proof then can someone kindly reference that? I haven't been able to find that..

• Do we know anything about say showing something like,

$max(f_{Max-Cut(G)}) \geq (\alpha_{GW} + \text{something positive}) \overline{sos}_{\text{something greater than} 2 }(f_{Max-Cut(G)})$ ?

The quadratic sum-of-squares relaxation of Max-Cut should indeed work out to be equivalent to the SDP that Goemans and Williamson solve. I encourage you to work this out yourself. This means that the Goemans-Williamson analysis indeed shows the inequality you mention.

You ask whether degree-2 SoS is a rewriting of the Goemans-Williamson rounding. It isn't. Rounding is a completely separate issue. Degree-2 SoS is a rewriting of the SDP that Goemans and Williamson solve. Rounding is how we bound the integrality gap.

Assuming the Unique Games Conjecture, $\alpha_{GW}$ is the optimal approximation ratio achievable in polynomial time. Since optimizing degree $d$ sum-of-squares can be done in time $O(n^{O(d)})$, this implies (assuming UGC) that every constant degree $d$ has the same integrality gap $\alpha_{GW}$ in the worst case.

• (1) I don't see the relation between the SDP that the GW rounds and what you call the "quadratic sos relaxation of Max-Cut". Also the SDP doesn't know the 0.878 thing since that comes from the GW rounding - that makes it more non-obvious as to how the SDP alone can give this SOS inequality which seems to know the 0.878 thing. (2) I know this UGC statement - but I wonder if on any special but non-trivial class of graphs this 0.878 has been improved by a degree > 2 SOS (or maybe even by a degree = 2 SOS) – gradstudent Feb 15 '16 at 17:46
• I mean one can always write down a SDP formulation of the question of finding the Lassere map at degree 2 for the max-cut constraints - but that is yet another SDP than the SDP that Max-Cut rounds - how is the SDP alone going to know this 0.878 thing? – gradstudent Feb 15 '16 at 17:51
• For (2), take a look at this survey: math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf. – Yuval Filmus Feb 15 '16 at 17:51
• For (1), $\alpha_{GW}$ is the integrality gap of the Goemans-Williamson relaxation. It's a property relaxation, not of the rounding. – Yuval Filmus Feb 15 '16 at 17:52
• Also, you can take a look at notes of Barak: boazbarak.org/sos/files/lec2d.pdf. However, I encourage you to work this out yourself. This is the only way to really understand it. – Yuval Filmus Feb 15 '16 at 17:55