20160111
On the sumofsquares degree of symmetric quadratic functions
Publication
Publication
We study how well functions over the boolean hypercube of the form $f_k(x)=(xk)(xk1)$ can be approximated by sums of squares of lowdegree polynomials, obtaining good bounds for the case of approximation in $\ell_{\infty}$norm as well as in $\ell_1$norm. We describe three complexitytheoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sumofsquares degree lower bounds on $\ell_1$approximation of $f_k$; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from his work; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
Additional Metadata  

IEEE Conference on Computational Complexity  
Organisation  Algorithms and Complexity 
Lee, T. J, Prakash, A, de Wolf, R.M, & Yuen, H. (2016). On the sumofsquares degree of symmetric quadratic functions.
