Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Low degree testing over the reals

Arora, Vipul ; Bhattacharyya, Arnab ; Fleming, Noah LU orcid ; Kelman, Esty and Yoshida, Yuichi (2022) p.738-792
Abstract
We study the problem of testing whether a function f:R^n→R 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 Rn 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/ε)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 ε with respect to D. Our result also holds under mild assumptions when we receive only a polynomial number of bits of... (More)
We study the problem of testing whether a function f:R^n→R 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 Rn 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/ε)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 ε 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. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
edition
2023
pages
55 pages
publisher
Society for Industrial and Applied Mathematics
DOI
10.48550/arXiv.2204.08404
language
English
LU publication?
no
id
16ea052a-c557-4a04-99de-030914c9c44f
date added to LUP
2025-11-05 15:57:46
date last changed
2026-08-17 12:53:41
@inproceedings{16ea052a-c557-4a04-99de-030914c9c44f,
  abstract     = {{We study the problem of testing whether a function f:R^n→R 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 Rn from which we can draw samples. In contrast to previous work, we do not assume that D has finite support.<br/>We design a tester that given query access to f, and sample access to D, makes (d/ε)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 ε 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.}},
  author       = {{Arora, Vipul and Bhattacharyya, Arnab and Fleming, Noah and Kelman, Esty and Yoshida, Yuichi}},
  booktitle    = {{Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}},
  language     = {{eng}},
  pages        = {{738--792}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  title        = {{Low degree testing over the reals}},
  url          = {{http://dx.doi.org/10.48550/arXiv.2204.08404}},
  doi          = {{10.48550/arXiv.2204.08404}},
  year         = {{2022}},
}