If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, where $L = I - A/d$, equals $4E(S,\bar{S})/d$. So trying to maximize $\langle x,Lx \rangle$ over $x \in \{1,-1\}^{|V|}$ maximizes the number of edges crossing across the cut, $(S,\bar{S})$.
With this set-up the Goemans–Williamson algorithm is stated in the sum-of-squares (SOS) literature as the claim that there exists a polynomial-time algorithm such that one can output a vector $z \in \{ \pm 1 \}^{\vert V \vert }$ such that $\langle z,Lz \rangle \geq 2n(1-f_{GW}(\epsilon))$ where $f_{GW}(\epsilon) \leq 10\sqrt{\epsilon}$ provided one is given a degree-2 pseudo-distribution such that $\tilde {\mathbb{E}} [x_i ^2] =1, \tilde {\mathbb{E}} [\langle x, Lx \rangle ] \geq 2n(1-\epsilon)$
So naturally the question arises as to from where does one get such a degree-2 pseudo-distribution? The implicit claim seems to be that there exists a "degree-2 SOS algorithm" which when run on these constraints $\{ x_i^2 =1, \langle x, Lx\rangle = 2n(1-\epsilon)\}$ will generate this "degree-2 pseudo-distribution". This apparently seems to be set up to be a semidefinite programming (SDP) question and hence one basically has to solve a SDP to get this pseudo-distribution!
- So what is the advantage of the SOS point of view here if one has to anyway run a SDP to get this degree-2 pseudo distribution?
- Also can someone point out an explicit reference about what exactly is this "degree-2 SOS algorithm" which will run on these constraints to give me the "degree-2 pseudo-distribution"?