2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (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) $\endgroup$ – gradstudent Feb 15 '16 at 17:46
  • $\begingroup$ 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? $\endgroup$ – gradstudent Feb 15 '16 at 17:51
  • $\begingroup$ For (2), take a look at this survey: math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf. $\endgroup$ – Yuval Filmus Feb 15 '16 at 17:51
  • $\begingroup$ For (1), $\alpha_{GW}$ is the integrality gap of the Goemans-Williamson relaxation. It's a property relaxation, not of the rounding. $\endgroup$ – Yuval Filmus Feb 15 '16 at 17:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 15 '16 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.