# Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?

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?

• 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. – Joe Bebel Oct 26 '15 at 23:02
• 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. – Sasho Nikolov Oct 27 '15 at 0:33