<p>I see the confusion, but I think the document you provided pretty well explains what is meant: solving MAXCUT on a graph <span class="math-container">$G$</span> is equivalent to finding the smallest value of <span class="math-container">$c$</span> such that <span class="math-container">$c-f_G(x)\geq 0$</span> for every <span class="math-container">$x\in \{-1,1\}^n$</span>. As you write, it is trivially true that <span class="math-container">$c^*=\mathsf{OPT}(G)$</span> is the optimal value where this holds by definition, but for one, you want to <em>determine the value of <span class="math-container">$\mathsf{OPT}(G)$</span> explicitly</em>, and equally as important, <em>there will not in general be a degree 2 sum-of-squares proof for any <span class="math-container">$c$</span> better than <span class="math-container">$\mathsf{OPT}(G)/.878$</span></em> (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 <span class="math-container">$\{-1,1\}^n$</span> for any <span class="math-container">$c\geq\mathsf{OPT}(G)/.878$</span> (which is what the work in the literature you reference establishes), so by doing binary search, you can algorithmically determine this looser quantity efficiently.</p>

CC BY-SA 4.0
2020-09-29T22:03:09.303Z
2020-09-29T22:03:09.303Z
Jason Gaitonde
<p>We say that <span class="math-container">$f$</span> has a degree <span class="math-container">$2d$</span> sum-of-squares certificate if <span class="math-container">$f=\sum_{i=1}^r (g_i(x))^2$</span>, where for each <span class="math-container">$i\in[r]$</span>, we have that <span class="math-container">$g_i$</span> is a polynomial of degree at most <span class="math-container">$d$</span>. Thus showing that <span class="math-container">$f$</span> has a sum-of-squares certificate is one way of showing that <span class="math-container">$f\ge 0$</span>.</p>
<p>Let <span class="math-container">$f_G(x)=\frac{1}{4}\sum_{(u,v)\in E}(x_u-x_v)^2$</span> for <span class="math-container">$x_u\in\{\pm1\}$</span> be the cut size function for an input vector <span class="math-container">$x\in\mathbb{F}_2^n$</span>, denoting the side of the vertices across a cut and let <span class="math-container">$\mathsf{OPT}(G)=\max_x f_G(x)$</span>.</p>
<p>Why does literature (e.g., <a href="http://web.stanford.edu/class/cs369h/lectures/lec5.pdf" rel="nofollow noreferrer">http://web.stanford.edu/class/cs369h/lectures/lec5.pdf</a>) go through work of showing that there exists a degree 2 sum-of-squares certificate for <span class="math-container">$\frac{\mathsf{OPT}(G)}{0.878}-f_G(x)$</span>? Isn't this vacuously true since <span class="math-container">$\frac{\mathsf{OPT}(G)}{0.878}\ge\mathsf{OPT}(G)\ge f_G(x)$</span> or is the input vector <span class="math-container">$x$</span> to <span class="math-container">$f_G(x)$</span> relaxed in this case, i.e., <span class="math-container">$x\in\mathbb{R}^n$</span>? 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 <span class="math-container">$0.878-\epsilon$</span> approximation?</p>
<p>Thanks in advance!</p>

CC BY-SA 4.0
2020-09-29T20:43:33.973Z
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
CC BY-SA 4.0
2020-09-29T20:59:38.543Z
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
<max-cut><sum-of-squares>
Sum-of-Squares Certificates
learning
# Sum-of-Squares Certificates

(Asked by: username_0 on 2020-09-29)

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!

**Tags:** max-cut, sum-of-squares
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-09-29. Score: 1 | Accepted answer

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.


---

