- On the sum-of-squares degree of symmetric quadratic functions
- Leibniz International Proceedings in Informatics
- Article number
- Number of pages
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
We study how well functions over the boolean hypercube of the form fk(x) = (|x|-k)(|x|-k-1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in l∞-norm as well as in l1-norm. We describe three complexity-theoretic 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 sum-of-squares degree lower bounds on l1-approximation of fk; (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 ; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
- go to publisher's site
- 31st Conference on Computational Complexity : CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, edited by Ran Raz.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.