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

DOI10.4230/LIPICS.CCC.2016.17zbMATH Open1380.68203arXiv1601.02311OpenAlexW2963518689MaRDI QIDQ5368751FDOQ5368751

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

Publication date: 10 October 2017

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.

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)

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Harmonicity and invariance on slices of the Boolean cube
• On effective determination of symmetric-square lifts
• Symmetric sums of squares over \(k\)-subset hypercubes
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Sum of Squares Bounds for the Empty Integral Hull Problem
• On symmetric square values of quadratic polynomials
• Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
• From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• 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)