7
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 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 Oct 26 '15 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$ – Sasho Nikolov Oct 27 '15 at 0:33

Your Answer

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

Browse other questions tagged or ask your own question.