Please use this identifier to cite or link to this item:
Title: On the sum-of-squares degree of symmetric quadratic functions
Authors: de Wolf, Ronald
Yuen, Henry
Lee, Troy
Prakash, Anupam
Keywords: Sum-of-squares Degree
Approximation Theory
Issue Date: 2016
Source: Lee, T., Prakash, A., de Wolf, R., & Yuen, H. (2016). On the sum-of-squares degree of symmetric quadratic functions. Leibniz International Proceedings in Informatics, 50, 17-. doi:10.4230/LIPIcs.CCC.2016.17
Series/Report no.: Leibniz International Proceedings in Informatics
Abstract: We study how well functions over the boolean hypercube of the form f_k(x)=(lxl-k)(lxl-k-1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in l_{infinity}-norm as well as in l_1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer [Lee/Raghavendra/Steurer, STOC 2015] 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 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 [Grigoriev, Comp. Compl. 2001]; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
DOI: 10.4230/LIPIcs.CCC.2016.17
Rights: © 2016 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
On the sum-of-squares degree of symmetric quadratic functions.pdf699.31 kBAdobe PDFThumbnail

Citations 20

Updated on Mar 8, 2021

Citations 50

Updated on Mar 9, 2021

Page view(s)

Updated on May 24, 2022

Download(s) 50

Updated on May 24, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.