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

<ul>
<li><a href="https://www.cs.cornell.edu/~dsteurer/papers/sosround.pdf" rel="nofollow">Rounding Sum-of-Squares Relaxations</a></li>
<li><a href="http://arxiv.org/pdf/1507.06370v2.pdf" rel="nofollow">Sum-of-Squares Lower Bounds for Sparse PCA</a></li>
</ul>

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

CC BY-SA 3.0
2015-10-26T23:02:50.800Z
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
CC BY-SA 3.0
2015-10-27T00:33:01.020Z
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
<cc.complexity-theory><complexity-classes><lower-bounds><sum-of-squares>
Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?
Steve
# Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?

(Asked by: username_0 on 2015-10-26)

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

* [Rounding Sum-of-Squares Relaxations](https://www.cs.cornell.edu/~dsteurer/papers/sosround.pdf)
* [Sum-of-Squares Lower Bounds for Sparse PCA](http://arxiv.org/pdf/1507.06370v2.pdf)

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

**Tags:** cc.complexity-theory, complexity-classes, lower-bounds, sum-of-squares

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

