Low Degree Testing over the Reals

Vipul Arora, Arnab Bhattacharyya, Noah Fleming +2

We study the problem of testing whether a function $f:{\mathbb{R}}^n\to \mathbb{R}$ is a polynomial of degree at most $d$ in the \emph{distribution-free} testing model. Here, the d…