Low Degree Testing over the Reals

Add to your list(s) Download to your calendar using vCal

• Vipul Arora (NUS)
• Wednesday 25 September 2024, 11:00-12:00
• Computer Laboratory, William Gates Building, FW26.

If you have a question about this talk, please contact Tom Gur.

We study the problem of testing whether a function $f: \realsⁿ \to \reals$ 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 $\realsⁿ$ 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/\eps)$ 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 $\eps$ 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.

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

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, FW26
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.