Sydney Algorithms and Theory of Computation seminar : Arora -- Low Degree Testing over the Reals

Time and Date: Tuesday, 6 June, 11am 

Location: building J12, room 124, and online 

Zoom link: https://uni-sydney.zoom.us/j/82281175309?from=addon

Title: Low Degree Testing over the Reals

Abstract: We study the problem of testing whether a function $f:
\reals^n \to \reals$ 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 $\reals^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 $\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 $\mathfrac{2}{3}$ if every degree-$d$ polynomial $P$
disagrees with $f$ on a set of mass at least $\eps$ 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.

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