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

Question

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)})$ ?

Answer 1

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.