Low Degree Testing over the Reals
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida · Society for Industrial and Applied Mathematics eBooks · 2023
We study the problem of testing whether a function f : ℝn → ℝ 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 ℝn 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/ε) 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 ε 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. * The arXiv version of the paper can be accessed at https://arxiv.org/abs/2204.08404