English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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-degreepolynomials, obtaining good bounds for the case of approximation in$\ell_{\infty}$-norm as well as in $\ell_1$-norm. We describe threecomplexity-theoretic applications: (1) a proof that the recent breakthroughlower bound of Lee, Raghavendra, and Steurer on the positive semidefiniteextension complexity of the correlation and TSP polytopes cannot be improvedfurther by showing better sum-of-squares degree lower bounds on$\ell_1$-approximation of $f_k$; (2) a proof that Grigoriev's lower bound onthe degree of Positivstellensatz refutations for the knapsack problem isoptimal, answering an open question from his work; (3) bounds on the querycomplexity of quantum algorithms whose expected output approximates suchfunctions.

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