On the sum-of-squares degree of symmetric quadratic functions
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 applica...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/90218 http://hdl.handle.net/10220/47238 |
| _version_ | 1811678926277181440 |
|---|---|
| author | de Wolf, Ronald Yuen, Henry Lee, Troy Prakash, Anupam |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences de Wolf, Ronald Yuen, Henry Lee, Troy Prakash, Anupam |
| author_sort | de Wolf, Ronald |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:01:01Z |
| format | Journal Article |
| id | ntu-10356/90218 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:01:01Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/902182023-02-28T19:24:13Z On the sum-of-squares degree of symmetric quadratic functions de Wolf, Ronald Yuen, Henry Lee, Troy Prakash, Anupam School of Physical and Mathematical Sciences Sum-of-squares Degree Approximation Theory DRNTU::Science::Physics 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. NRF (Natl Research Foundation, S’pore) Published version 2018-12-27T04:51:15Z 2019-12-06T17:43:21Z 2018-12-27T04:51:15Z 2019-12-06T17:43:21Z 2016 Journal Article 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 https://hdl.handle.net/10356/90218 http://hdl.handle.net/10220/47238 10.4230/LIPIcs.CCC.2016.17 en Leibniz International Proceedings in Informatics © 2016 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY. 31 p. application/pdf |
| spellingShingle | Sum-of-squares Degree Approximation Theory DRNTU::Science::Physics de Wolf, Ronald Yuen, Henry Lee, Troy Prakash, Anupam On the sum-of-squares degree of symmetric quadratic functions |
| title | On the sum-of-squares degree of symmetric quadratic functions |
| title_full | On the sum-of-squares degree of symmetric quadratic functions |
| title_fullStr | On the sum-of-squares degree of symmetric quadratic functions |
| title_full_unstemmed | On the sum-of-squares degree of symmetric quadratic functions |
| title_short | On the sum-of-squares degree of symmetric quadratic functions |
| title_sort | on the sum of squares degree of symmetric quadratic functions |
| topic | Sum-of-squares Degree Approximation Theory DRNTU::Science::Physics |
| url | https://hdl.handle.net/10356/90218 http://hdl.handle.net/10220/47238 |
| work_keys_str_mv | AT dewolfronald onthesumofsquaresdegreeofsymmetricquadraticfunctions AT yuenhenry onthesumofsquaresdegreeofsymmetricquadraticfunctions AT leetroy onthesumofsquaresdegreeofsymmetricquadraticfunctions AT prakashanupam onthesumofsquaresdegreeofsymmetricquadraticfunctions |