Abstract

We study the problem of testing whether a function $f: \realsⁿ \to \reals$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $D$ over $\realsⁿ$ from which we can draw samples. In contrast to previous work, we do not assume that $D$ has finite support. We design a tester that given query access to $f$, and sample access to $D$, makes $\poly(d/\eps)$ many queries to $f$, accepts with probability $1$ if $f$ is a polynomial of degree $d$, and rejects with probability at least $2/3$ if every degree-$d$ polynomial $P$ disagrees with $f$ on a set of mass at least $\eps$ with respect to $D$. Our result also holds under mild assumptions when we receive only a polynomial number of bits of precision for each query to $f$, or when $f$ can only be queried on rational points representable using a logarithmic number of bits. Along the way, we prove a new stability theorem for multivariate polynomials that may be of independent interest.

This is a joint work with Arnab Bhattacharyya, Esty Kelman, Noah Fleming, and Yuichi Yoshida, and appeared in SODA ’23.