On the sum-of-squares degree of symmetric quadratic functions

Troy Lee, Anupam Prakash, Ronald de Wolf +1

We study how well functions over the boolean hypercube of the form $f_k(x)=(|x|-k)(|x|-k-1)$ can be approximated by sums of squares of low-degree polynomials, obtaining good bounds…