论文标题
对真实的低度测试
Low Degree Testing over the Reals
论文作者
论文摘要
我们研究了测试函数$ f的问题：\ mathbb {r}^n \ to \ mathbb {r} $在\ emph {Distribution-free}测试模型中最多是$ d $的多项式。在这里，函数之间的距离是根据$ \ mathbb {r}^n $在$ \ mathbb上的未知分布$ \ mathcal {d} $来衡量的。与以前的工作相反，我们不认为$ \ Mathcal {D} $具有有限的支持。 我们设计了一个测试仪，可以给出查询访问$ f $的测试仪，并示例访问$ \ Mathcal {d} $，使$（d/\ varepsilon）^{o（1）} $对$ f $的许多查询，接受概率$ 1 $ $ 1 $，如果$ f $是$ d $ $ d $ $ d $ d $ d $ d $ d $ d $ d $ d $ d $ 2/3相对于$ \ Mathcal {d} $，一组质量上的$ f $至少不同意$ f $。当我们仅收到每个查询到$ f $的多项式精确度的精度时，或者只能使用对数数量的位来表示有理点时，我们的结果也会保持在温和的假设下。一路上，我们证明了可能具有独立关注的多元多项式定理。
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 distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast to previous work, we do not assume that $\mathcal{D}$ has finite support. We design a tester that given query access to $f$, and sample access to $\mathcal{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 $\mathcal{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.
