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...
محفوظ في:
المؤلفون الرئيسيون: | de Wolf, Ronald, Yuen, Henry, Lee, Troy, Prakash, Anupam |
---|---|
مؤلفون آخرون: | School of Physical and Mathematical Sciences |
التنسيق: | مقال |
اللغة: | English |
منشور في: |
2018
|
الموضوعات: | |
الوصول للمادة أونلاين: | https://hdl.handle.net/10356/90218 http://hdl.handle.net/10220/47238 |
الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
المؤسسة: | Nanyang Technological University |
اللغة: | English |
مواد مشابهة
-
Integers as sum of squares
بواسطة: Calusin, Rosalie Coney E., وآخرون
منشور في: (1995) -
Representations of Integers as Sums of 32 Squares
بواسطة: Chan, H.H., وآخرون
منشور في: (2014) -
An odd square as a sum of an odd number of odd squares
بواسطة: Chan, H.H., وآخرون
منشور في: (2014) -
Saddlepoint approximations for studentized compound Poisson sums with no moment conditions in audit sampling
بواسطة: Zhou, G.L., وآخرون
منشور في: (2014) -
Sums of two squares
بواسطة: Luy, Maribeth, وآخرون
منشور في: (1992)