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

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

Detaylı Bibliyografya
Asıl Yazarlar:	de Wolf, Ronald, Yuen, Henry, Lee, Troy, Prakash, Anupam
Diğer Yazarlar:	School of Physical and Mathematical Sciences
Materyal Türü:	Journal Article
Dil:	English
Baskı/Yayın Bilgisi:	2018
Konular:	Sum-of-squares Degree Approximation Theory DRNTU::Science::Physics
Online Erişim:	https://hdl.handle.net/10356/90218 http://hdl.handle.net/10220/47238

Benzer Materyaller

Recursive determination of the enumerator for sums of three squares
Yazar:: John A. Ewell
Baskı/Yayın Bilgisi: (2000-01-01)

The least-squares approximation and related topics /
Yazar:: Vanicek, Petr, 1935-, ve diğerleri
Baskı/Yayın Bilgisi: (1972)

Minimum atom-bond sum-connectivity index of unicyclic graphs with maximum degree
Yazar:: Palaniyappan Nithya,, ve diğerleri
Baskı/Yayın Bilgisi: (2024-04-01)

stability analysis of fuzzy Polynomial fractional differential Systems using Sum-of-Squares
Yazar:: hassan yaghoubi, ve diğerleri
Baskı/Yayın Bilgisi: (2022-12-01)

Exact distribution of the sum of two correlated chi-square variables and its application
Yazar:: ANWAR H. JOARDER, ve diğerleri
Baskı/Yayın Bilgisi: (2013-09-01)

Sums of squares of integers /
Yazar:: Moreno, Carlos J., 1946-, ve diğerleri
Baskı/Yayın Bilgisi: (2006)

Order estimates of the uniform approximations by Zygmund sums on the classes of convolutions of periodic functions
Yazar:: A.S. Serdyuk, ve diğerleri
Baskı/Yayın Bilgisi: (2021-04-01)

Estimation of the Region of Attraction of Polynomial Swing Equation Using Sum of Squares Theory
Yazar:: Jing Li, ve diğerleri
Baskı/Yayın Bilgisi: (2024-02-01)

High-Performance Hybrid Algorithm for Minimum Sum-of-Squares Clustering of Infinitely Tall Data
Yazar:: Ravil Mussabayev, ve diğerleri
Baskı/Yayın Bilgisi: (2024-06-01)

The hybrid power mean of the generalized Gauss sums and the generalized two-term exponential sums
Yazar:: Xue Han, ve diğerleri
Baskı/Yayın Bilgisi: (2024-01-01)

Approximation and the Multidimensional Moment Problem
Yazar:: Octav Olteanu
Baskı/Yayın Bilgisi: (2025-01-01)

Triple Symmetric Sums of Circular Binomial Products
Yazar:: Marta Na Chen, ve diğerleri
Baskı/Yayın Bilgisi: (2024-07-01)

Parameterized Finite Binomial Sums
Yazar:: Necdet Batır, ve diğerleri
Baskı/Yayın Bilgisi: (2024-08-01)

Dim sum kitchen /
Yazar:: Tan, Melody
Baskı/Yayın Bilgisi: (2009)

Generalized H-fold sumset and Subsequence sum
Yazar:: Mohan, ve diğerleri
Baskı/Yayın Bilgisi: (2024-02-01)

Using sums-of-squares to prove Gaussian product inequalities
Yazar:: Russell Oliver, ve diğerleri
Baskı/Yayın Bilgisi: (2024-06-01)

Eisenstein series and convolution sums
Yazar:: Aygin, Zafer Selcuk
Baskı/Yayın Bilgisi: (2020)

Finite and Symmetric Euler Sums and Finite and Symmetric (Alternating) Multiple <i>T</i>-Values
Yazar:: Jianqiang Zhao
Baskı/Yayın Bilgisi: (2024-03-01)

Approximations [filem]
Baskı/Yayın Bilgisi: (1971)

Approximations [kasetvideo]
Baskı/Yayın Bilgisi: (1971)

Deletion of a vertex in even sum domination
Yazar:: Alfatlawi Ahllam A., ve diğerleri
Baskı/Yayın Bilgisi: (2024-03-01)

A new reciprocity formula of Dedekind sums and its applications
Yazar:: Zhuoyu Chen, ve diğerleri
Baskı/Yayın Bilgisi: (2024-04-01)

A generalization of a theorem by Cheo and Yien concerning digital sums
Yazar:: Curtis N. Cooper, ve diğerleri
Baskı/Yayın Bilgisi: (1986-01-01)

Research progress on correction techniques for coincidence summing effect in γ-ray spectrometry
Yazar:: FAN Yuanqing, ve diğerleri
Baskı/Yayın Bilgisi: (2024-03-01)

Cyclotomic equations and square properties in rings
Yazar:: Benjamin Fine
Baskı/Yayın Bilgisi: (1986-01-01)

A remark with regard to inequalities for some sums
Yazar:: Simeunović Dragomir M.
Baskı/Yayın Bilgisi: (2014-01-01)

On the general solution of a functional equation connected to sum form information measures on open domain—III
Yazar:: Pl. Kannappan, ve diğerleri
Baskı/Yayın Bilgisi: (1986-01-01)

Covering energy, linear sum and vertical sum of posets
Yazar:: Vandana P. Bhamre, ve diğerleri
Baskı/Yayın Bilgisi: (2024-07-01)

Some properties of power sums of truncated normal random variables /
Yazar:: 265334 Nasell, Ingemar

An Estimation of Exponential Sums Associated with a Cubic Form Polynomial
Yazar:: Heng, Swee Huay
Baskı/Yayın Bilgisi: (1999)

On Large Sum-Free Sets: Revised Bounds and Patterns
Yazar:: Renato Cordeiro de Amorim
Baskı/Yayın Bilgisi: (2024-12-01)

Primality proving with Gauss and Jacobi sums
Yazar:: Andrzej Chmielowiec
Baskı/Yayın Bilgisi: (2004-12-01)

One kind two-term exponential sums weighted by third-order character
Yazar:: Guohui Chen, ve diğerleri
Baskı/Yayın Bilgisi: (2024-03-01)

Group Constant-Sum Spectrum of Nearly Regular Graphs
Yazar:: Tao-Ming Wang
Baskı/Yayın Bilgisi: (2025-01-01)

Optimal Piecewise Polynomial Approximation for Minimum Computing Cost by Using Constrained Least Squares
Yazar:: Jieun Song, ve diğerleri
Baskı/Yayın Bilgisi: (2024-06-01)

On the number of nonnegative sums for certain function
Yazar:: Ku, Cheng Yeaw, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

Average Size of Ramanujan Sum Associated with Divisor Function
Yazar:: Xin Li, ve diğerleri
Baskı/Yayın Bilgisi: (2025-02-01)

Analytical Relations and Statistical Estimations for Sums of Powered Integers
Yazar:: Stan Lipovetsky
Baskı/Yayın Bilgisi: (2025-01-01)

Generalized quadratic Gauss sums and their 2mth power mean
Yazar:: Cui Dewang, ve diğerleri
Baskı/Yayın Bilgisi: (2024-11-01)

Finite algorithms in optimization and data analysis /
Yazar:: Osborne, M. R. (Michael Robert)
Baskı/Yayın Bilgisi: (1985)