In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g.

I was curious why this number $4$ seems so crucial here. What is the difficulty of higher order SoS relaxations?

  • 2
    $\begingroup$ I don't know that the constant 4 is very special here, it merely represents the 'state of the art'. In some sense degree 2 SoS was the 'state of the art' for a long time as well, and it is of intense interest when degree 2 SoS is optimal and when degree 4 gives improvement. Higher degree would certainly be interesting, but even today we have enough trouble handling the degree 4 case. $\endgroup$
    – Joe Bebel
    Commented Oct 26, 2015 at 23:02
  • 5
    $\begingroup$ My, possiibly incorrect, understanding is that degree 2 is fairly well understood: some version of random projection rounding is often optimal. Then degree 4 is the lowest even degree that is higher than 2 :). This is the usual game played in mathematics: let's understand the simplest problem that we currently can't solve. $\endgroup$ Commented Oct 27, 2015 at 0:33


Your Answer

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