Sum-of-Squares Certificates

Question

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?

Thanks in advance!

Answer 1

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.