# Sum-of-Squares Certificates

We say that $$f$$ has a degree $$2d$$ sum-of-squares certificate if $$f=\sum_{i=1}^r (g_i(x))^2$$, where for each $$i\in[r]$$, we have that $$g_i$$ is a polynomial of degree at most $$d$$. Thus showing that $$f$$ has a sum-of-squares certificate is one way of showing that $$f\ge 0$$.

Let $$f_G(x)=\frac{1}{4}\sum_{(u,v)\in E}(x_u-x_v)^2$$ for $$x_u\in\{\pm1\}$$ be the cut size function for an input vector $$x\in\mathbb{F}_2^n$$, denoting the side of the vertices across a cut and let $$\mathsf{OPT}(G)=\max_x f_G(x)$$.

Why does literature (e.g., http://web.stanford.edu/class/cs369h/lectures/lec5.pdf) go through work of showing that there exists a degree 2 sum-of-squares certificate for $$\frac{\mathsf{OPT}(G)}{0.878}-f_G(x)$$? Isn't this vacuously true since $$\frac{\mathsf{OPT}(G)}{0.878}\ge\mathsf{OPT}(G)\ge f_G(x)$$ or is the input vector $$x$$ to $$f_G(x)$$ relaxed in this case, i.e., $$x\in\mathbb{R}^n$$? Is it correct that any algorithmic statement, such as the Goemans-Williamson algorithm, still needs a separate statement of correctness independent of the degree 2 sum-of-squares certificate? If so, is the purpose of the certificate to lay the groundwork for showing that any minimally lossy rounding algorithm achieves $$0.878-\epsilon$$ approximation?

• What is meant by a "certificate for $\frac{\textsf{OPT}(G)}{0.878}-f_g(x)$? What does it certify? That a given cut $x$ is within $0.878$ of the optimum? Can you explain why you think it would be vacuously true? Lastly, please provide a reference to "literature", where you found the claim that there is a degree-$2$ sum-of-square certificate. This will allow people to help you better. – Lieuwe Vinkhuijzen Sep 29 '20 at 20:43
• Thanks, I've added a reference, commented on what an SOS certificate certifies for a general function $f$ and explained why I think it's vacuous (but obviously it must not be). Sorry for the confusion. – learning Sep 29 '20 at 20:59
I see the confusion, but I think the document you provided pretty well explains what is meant: solving MAXCUT on a graph $$G$$ is equivalent to finding the smallest value of $$c$$ such that $$c-f_G(x)\geq 0$$ for every $$x\in \{-1,1\}^n$$. As you write, it is trivially true that $$c^*=\mathsf{OPT}(G)$$ is the optimal value where this holds by definition, but for one, you want to determine the value of $$\mathsf{OPT}(G)$$ explicitly, and equally as important, there will not in general be a degree 2 sum-of-squares proof for any $$c$$ better than $$\mathsf{OPT}(G)/.878$$ (this doesn't rely on UGC or anything fancy like that; if I remember right, there are known hard examples that basically embed vectors in a high-dimensional sphere with edges that emulate where the GW algorithm has a tough time in the rounding and uses the isoperimetric inequality on the sphere to argue about the real optimal value). The point of doing the degree 2 sum-of-squares algorithm is that there for sure exists a degree 2 sum-of-squares certificate of this polynomial inequality over $$\{-1,1\}^n$$ for any $$c\geq\mathsf{OPT}(G)/.878$$ (which is what the work in the literature you reference establishes), so by doing binary search, you can algorithmically determine this looser quantity efficiently.