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!

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Sep 29, 2020 at 20:43
  • $\begingroup$ 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. $\endgroup$
    – learning
    Commented Sep 29, 2020 at 20:59

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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