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

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

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 -error polynomials for symmetric functions
• Algorithmic Polynomials
• Algorithmic polynomials

Cited in

(15)

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