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

2016/01/11 by Troy Lee, Lee, Troy, Anupam Prakash +5
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1601.02311

33 pages. Second version fixes some typos and adds references

arxiv created 2016/03/08 · arxiv updated 2016/03/09

Abstract

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 for the case of approximation in ℓ_∞-norm as well as in ℓ₁-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 ℓ₁-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.

Related

• Algorithmic Polynomials
• SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
• Classical lower bounds from quantum upper bounds
• Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
• Sum-of-squares proofs and the quest toward optimal algorithms