Abstract

We study how well functions over the boolean hypercube of the form fk(x)=(∣x∣−k)(∣x∣−k−1)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 ℓ∞\ell_{\infty}-norm as well as in ℓ1\ell_1-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 ℓ1\ell_1-approximation of fkf_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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.