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

DOI10.4230/LIPICS.CCC.2016.17MaRDI QIDQ5368751zbMATH OpenOpenAlexFDO

Authors Troy Lee, Anupam Prakash, Henry C. Yuen, Ronald de Wolf

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1601.02311

zbMATH Keywords

approximation theoryextension complexityPositivstellensatz refutations of knapsackquantum query complexity in expectationsum-of-squares degree

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Abstract computational complexity for mathematical programming problems (90C60) Approximation by polynomials (41A10) Boolean programming (90C09)

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 $el{l}_{infty}$-norm as well as in $el{l}_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 $el{l}_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.

Recommendations

• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares hierarchies for binary polynomial optimization
• A note on quantum algorithms and the minimal degree of \(\varepsilon\)-error polynomials for symmetric functions
• Algorithmic Polynomials
• Algorithmic polynomials

Cited in

(13)

• Harmonicity and invariance on slices of the Boolean cube
• On effective determination of symmetric-square lifts
• Symmetric sums of squares over \(k\)-subset hypercubes
• Sum of squares lower bounds from symmetry and a good story
• Sum-of-squares bounds via Boolean function analysis
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Exact quantum query complexity of \(\mathrm{EXACT}_{k,l}^n\)
• Query complexity in expectation
• Sum of Squares Bounds for the Empty Integral Hull Problem
• On symmetric square values of quadratic polynomials
• From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares hierarchies for binary polynomial optimization

This page was built for publication: On the sum-of-squares degree of symmetric quadratic functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368751)