Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/90218
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | de Wolf, Ronald | en |
dc.contributor.author | Yuen, Henry | en |
dc.contributor.author | Lee, Troy | en |
dc.contributor.author | Prakash, Anupam | en |
dc.date.accessioned | 2018-12-27T04:51:15Z | en |
dc.date.accessioned | 2019-12-06T17:43:21Z | - |
dc.date.available | 2018-12-27T04:51:15Z | en |
dc.date.available | 2019-12-06T17:43:21Z | - |
dc.date.issued | 2016 | en |
dc.identifier.citation | 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 | en |
dc.identifier.uri | https://hdl.handle.net/10356/90218 | - |
dc.description.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. | en |
dc.description.sponsorship | NRF (Natl Research Foundation, S’pore) | en |
dc.format.extent | 31 p. | en |
dc.language.iso | en | en |
dc.relation.ispartofseries | Leibniz International Proceedings in Informatics | en |
dc.rights | © 2016 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY. | en |
dc.subject | Sum-of-squares Degree | en |
dc.subject | Approximation Theory | en |
dc.subject | DRNTU::Science::Physics | en |
dc.title | On the sum-of-squares degree of symmetric quadratic functions | en |
dc.type | Journal Article | en |
dc.contributor.school | School of Physical and Mathematical Sciences | en |
dc.identifier.doi | 10.4230/LIPIcs.CCC.2016.17 | en |
dc.description.version | Published version | en |
item.fulltext | With Fulltext | - |
item.grantfulltext | open | - |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
On the sum-of-squares degree of symmetric quadratic functions.pdf | 699.31 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
20
10
Updated on Mar 20, 2024
Web of ScienceTM
Citations
50
4
Updated on Oct 27, 2023
Page view(s)
410
Updated on Mar 28, 2024
Download(s) 50
48
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.