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

Lee, T; Prakash, A; De Wolf, R; Yuen, H

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

Lee, T

Prakash, A De Wolf, R Yuen, H

Permalink

Publication Type:: Journal Article
Citation:: Leibniz International Proceedings in Informatics, LIPIcs, 2016, 50, pp. 17:1-17:31
Issue Date:: 2016-05-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (699.31 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Prakash, A
dc.contributor.author	De Wolf, R
dc.contributor.author	Yuen, H
dc.date.accessioned	2022-08-01T07:47:38Z
dc.date.available	2022-08-01T07:47:38Z
dc.date.issued	2016-05-01
dc.identifier.citation	Leibniz International Proceedings in Informatics, LIPIcs, 2016, 50, pp. 17:1-17:31
dc.identifier.isbn	9783959770088
dc.identifier.issn	1868-8969
dc.identifier.uri	http://hdl.handle.net/10453/159447
dc.description.abstract	We study how well functions over the boolean hypercube of the form fk(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 '1-norm as well as in '1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer [19] 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 '1-approximation of fk; (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 [12]; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
dc.language	en
dc.relation.ispartof	Leibniz International Proceedings in Informatics, LIPIcs
dc.relation.isbasedon	10.4230/LIPIcs.CCC.2016.17
dc.rights	info:eu-repo/semantics/openAccess
dc.title	On the sum-of-squares degree of symmetric quadratic functions
dc.type	Journal Article
utslib.citation.volume	50
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
dc.date.updated	2022-08-01T07:47:36Z
pubs.publication-status	Published
pubs.volume	50

Abstract:

We study how well functions over the boolean hypercube of the form fk(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 '1-norm as well as in '1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer [19] 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 '1-approximation of fk; (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 [12]; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/159447