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

DOI10.4230/LIPIcs.CCC.2016.17zbMath1380.68203arXiv1601.02311OpenAlexW2963518689MaRDI QIDQ5368751

Henry C. Yuen, Anupam Prakash, Troy Lee, 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

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

Related Items (9)

Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ Symmetric sums of squares over \(k\)-subset hypercubes ⋮ Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Harmonicity and invariance on slices of the Boolean cube

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