3
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end.

You might be interested in Lee Raghavendra Steurer '14. 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – gradstudent Jan 18 '17 at 19:06
  • $\begingroup$ 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. $\endgroup$ – Chris Jones Jun 3 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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