Testing noisy low-degree polynomials for sparsity

Yiqiao Bao, Anindya De, Shivam Nadimpalli +2

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 polyn…