<p>We don't have integrality gaps even for Max-CUT, even for degree 4. See <a href="http://sumofsquares.org/public/lec03-1_lowerbound_maxcut.html" rel="nofollow noreferrer">Barak and Steurer's notes</a>, at the end.</p>

<p>You might be interested in <a href="https://arxiv.org/abs/1411.6317" rel="nofollow noreferrer">Lee Raghavendra Steurer '14</a>. They seem to be saying there can be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c &lt; 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there are instances of Max-CUT requiring higher degree. I lack the expertise to be sure I'm interpreting this correctly though.</p>

<p>Other than this, I don't know of any lower bounds for the degree of SOS that can solve Max-CUT exactly.</p>

CC BY-SA 3.0
2017-01-18T19:06:50.217Z
Thanks! What you say is what has been my understanding. But this looks peculiarly paradoxical to me. Think about it this way : Given that Max-CUT is NP-Hard how is it possible that no one has ever seen a graph which is outside even SOS_4 (thats a pretty weak level of the hierarchy!)? Has no one just maybe scanned through all possible small graphs of say size upto 10 and found one example? Is such an in-principle simple scan actually impossibly hard to do (even by softwares?) or is it that people have done such scans and no one has found any?
gradstudent
CC BY-SA 4.0
2019-06-03T18:10:51.517Z
You could almost certainly find a small graph where degree-4 SOS thinks the graph has a larger max cut than the true optimum by enumerating small examples like you say. This is because we shouldn't expect degree-4 SOS to solve Max-Cut exactly due to NP-hardness. However, the really interesting question is *how big* of an integrality gap can you find? Can you find instances where the true cut is 0.878 of the degree-4 SOS value (thus showing deg-4 is no stronger than deg-2)? But these instances might be large e.g. Feige-Schechtman instances would be pretty big to verify experimentally.
Chris Jones
CC BY-SA 3.0
2017-01-17T01:40:43.770Z
2017-01-17T01:40:43.770Z
Whosyourjay
<p>Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations? </p>

<hr>

<p>Or if we specialize to Max-CUT do we know of graphs whose Max-CUT polynomial needs high SOS degree to be solved? (Or if we at least know of integrality gaps for it for high SOS degree) </p>

<cc.complexity-theory><semidefinite-programming><max-cut><sum-of-squares>
SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?
gradstudent
# SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

(Asked by: username_0 on 2017-01-16)

Do we know of instances of $Max-2-Lin(\mathbb{Z}\_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations?

---

Or if we specialize to Max-CUT do we know of graphs whose Max-CUT polynomial needs high SOS degree to be solved? (Or if we at least know of integrality gaps for it for high SOS degree)

**Tags:** cc.complexity-theory, semidefinite-programming, max-cut, sum-of-squares

---

## 1 answers

### Answer by username_1 on 2017-01-17. Score: 3

We don't have integrality gaps even for Max-CUT, even for degree 4. See [Barak and Steurer's notes](http://sumofsquares.org/public/lec03-1_lowerbound_maxcut.html), at the end.

You might be interested in [Lee Raghavendra Steurer '14](https://arxiv.org/abs/1411.6317). They seem to be saying there can be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c < 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there are instances of Max-CUT requiring higher degree. I lack the expertise to be sure I'm interpreting this correctly though.

Other than this, I don't know of any lower bounds for the degree of SOS that can solve Max-CUT exactly.

> **Comments:**
> **username_0**: Thanks! What you say is what has been my understanding. But this looks peculiarly paradoxical to me. Think about it this way : Given that Max-CUT is NP-Hard how is it possible that no one has ever seen a graph which is outside even SOS_4 (thats a pretty weak level of the hierarchy!)? Has no one just maybe scanned through all possible small graphs of say size upto 10 and found one example? Is such an in-principle simple scan actually impossibly hard to do (even by softwares?) or is it that people have done such scans and no one has found any?  
> **username_2**: You could almost certainly find a small graph where degree-4 SOS thinks the graph has a larger max cut than the true optimum by enumerating small examples like you say. This is because we shouldn't expect degree-4 SOS to solve Max-Cut exactly due to NP-hardness. However, the really interesting question is *how big* of an integrality gap can you find? Can you find instances where the true cut is 0.878 of the degree-4 SOS value (thus showing deg-4 is no stronger than deg-2)? But these instances might be large e.g. Feige-Schechtman instances would be pretty big to verify experimentally.  

---

