{"ID":2843141,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.07835","arxiv_id":"2511.07835","title":"Testing noisy low-degree polynomials for sparsity","abstract":"We consider the problem of testing whether an unknown low-degree polynomial $p$ over $\\mathbb{R}^n$ is sparse versus far from sparse, given access to noisy evaluations of the polynomial $p$ at \\emph{randomly chosen points}. This is a property-testing analogue of classical problems on learning sparse low-degree polynomials with noise, extending the work of Chen, De, and Servedio (2020) from noisy \\emph{linear} functions to general low-degree polynomials. Our main result gives a \\emph{precise characterization} of when sparsity testing for low-degree polynomials admits constant sample complexity independent of dimension, together with a matching constant-sample algorithm in that regime. For any mean-zero, variance-one finitely supported distribution $\\boldsymbol{X}$ over the reals, degree $d$, and any sparsity parameters $s \\leq T$, we define a computable function $\\mathrm{MSG}_{\\boldsymbol{X},d}(\\cdot)$, and: - For $T \\ge \\mathrm{MSG}_{\\boldsymbol{X},d}(s)$, we give an $O_{s,\\boldsymbol{X},d}(1)$-sample algorithm that distinguishes whether a multilinear degree-$d$ polynomial over $\\mathbb{R}^n$ is $s$-sparse versus $\\varepsilon$-far from $T$-sparse, given examples $(\\boldsymbol{x},\\, p(\\boldsymbol{x}) + \\mathrm{noise})_{\\boldsymbol{x} \\sim \\boldsymbol{X}^{\\otimes n}}$. Crucially, the sample complexity is \\emph{completely independent} of the ambient dimension $n$. - For $T \\leq \\mathrm{MSG}_{\\boldsymbol{X},d}(s) - 1$, we show that even without noise, any algorithm given samples $(\\boldsymbol{x},p(\\boldsymbol{x}))_{\\boldsymbol{x} \\sim \\boldsymbol{X}^{\\otimes n}}$ must use $Ω_{\\boldsymbol{X},d,s}(\\log n)$ examples. Our techniques employ a generalization of the results of Dinur et al. (2007) on the Fourier tails of bounded functions over $\\{0,1\\}^n$ to a broad range of finitely supported distributions, which may be of independent interest.","short_abstract":"We consider the problem of testing whether an unknown low-degree polynomial $p$ over $\\mathbb{R}^n$ is sparse versus far from sparse, given access to noisy evaluations of the polynomial $p$ at \\emph{randomly chosen points}. This is a property-testing analogue of classical problems on learning sparse low-degree polynomi...","url_abs":"https://arxiv.org/abs/2511.07835","url_pdf":"https://arxiv.org/pdf/2511.07835v1","authors":"[\"Yiqiao Bao\",\"Anindya De\",\"Shivam Nadimpalli\",\"Rocco A. Servedio\",\"Nathan White\"]","published":"2025-11-11T05:11:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}