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...

Full description

Saved in:
Bibliographic Details
Main Authors: de Wolf, Ronald, Yuen, Henry, Lee, Troy, Prakash, Anupam
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2018
Subjects:
Online Access:https://hdl.handle.net/10356/90218
http://hdl.handle.net/10220/47238
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Be the first to leave a comment!
You must be logged in first