Testing noisy low-degree polynomials for sparsity

2025/11/11 by Bao, Yiqiao, De, Anindya, Nadimpalli, Shivam +2
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2511.07835

Abstract

We consider the problem of testing whether an unknown low-degree polynomial p over ℝⁿ is sparse versus far from sparse, given access to noisy evaluations of the polynomial p at 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 linear functions to general low-degree polynomials. Our main result gives a 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 \boldsymbolX over the reals, degree d, and any sparsity parameters s ≤ T, we define a computable function MSG_\boldsymbolX,d(⋅), and: - For T ≥ MSG_\boldsymbolX,d(s), we give an O_s,\boldsymbolX,d(1)-sample algorithm that distinguishes whether a multilinear degree-d polynomial over ℝⁿ is s-sparse versus ε-far from T-sparse, given examples (\boldsymbolx, p(\boldsymbolx) + noise)_\boldsymbolx ∼ \boldsymbolX^{⊗ n}. Crucially, the sample complexity is completely independent of the ambient dimension n. - For T ≤ MSG_\boldsymbolX,d(s) - 1, we show that even without noise, any algorithm given samples (\boldsymbolx,p(\boldsymbolx))_\boldsymbolx ∼ \boldsymbolX^{⊗ n} must use Ω_\boldsymbolX,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\ⁿ to a broad range of finitely supported distributions, which may be of independent interest.

Citations

• Robust testing of low-dimensional functions
• Testing noisy linear functions for sparsity
• Testing Halfspaces over Rotation-Invariant Distributions
• Is your function low-dimensional?
• Sparse Hierarchical Regression with Polynomials
• Sample-based high-dimensional convexity testing
• Settling the query complexity of non-adaptive junta testing
• Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
• Efficiently Testing Sparse GF(2) Polynomials

Related

• Testing noisy linear functions for sparsity
• Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
• Low Degree Testing over the Reals
• Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
• The Polynomial-Time Low-Degree Conjecture is False