# Low Degree Testing over the Reals

arXiv: https://arxiv.org/abs/2204.08404 · HTML: https://mlsanity.com/paper/2204.08404/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2022.

## Built on by (most cited first, 3 of 3)

- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Aligning Model Properties via Conformal Risk Control](https://mlsanity.com/paper/2406.18777/) (2024)
- [Oblivious Defense in ML Models: Backdoor Removal without Detection](https://mlsanity.com/paper/2411.03279/) (2024)

## Abstract (arXiv)

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 (d/varepsilon)O(1) 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 varepsilon 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.