Testing noisy low-degree polynomials for sparsity

Yiqiao Bao Anindya De Shivam Nadimpalli University of Pennsylvania University of Pennsylvania MIT [email protected] [email protected] [email protected] Rocco A. Servedio Nathan White Columbia University University of Pennsylvania [email protected] [email protected] · 2025

Read Testing noisy low-degree polynomials for sparsity by Yiqiao Bao Anindya De Shivam Nadimpalli University of Pennsylvania University of Pennsylvania MIT [email protected] [email protected] [email protected] Rocco A. Servedio Nathan White Columbia University University of Pennsylvania [email protected] [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07835.txt.

Description

Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco Servedio, and Nathan White ask how to test a polynomial for sparsity using noisy values. The unknown polynomial has low degree in many variables. A tester sees random points with noise added and must tell sparse cases from ones far from sparse.

The team gives an exact boundary for when a constant number of samples, independent of dimension, can suffice. Above that boundary they supply a matching constant sample algorithm. Below it, even noise free testing needs samples growing with dimension. Their Fourier tail tools may also help beyond this problem.

Catalog record

CREATORYiqiao Bao Anindya De Shivam Nadimpalli University of Pennsylvania University of Pennsylvania MIT [email protected] [email protected] [email protected] Rocco A. Servedio Nathan White Columbia University University of Pennsylvania [email protected] [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE220 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07835

Browse the full library · About the Tower of Babel