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
| CREATOR | 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] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 220 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07835