Explicit Lower Bounds Against $\Omega (n)$-Rounds of Sum-of-Squares

Max Hopkins, Ting-Chun Lin

We construct an explicit family of 3-XOR instances hard for $\Omega (n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit const…