BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Low Degree Testing over the Reals - Vipul Arora (NUS)
DTSTART:20240925T100000Z
DTEND:20240925T110000Z
UID:TALK220975@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:We study the problem of testing whether a function $f: \\reals
 ^n^ \\to \\reals$ is a polynomial of degree at most $d$ in the distributio
 n-free testing model. Here\, the distance between functions is measured wi
 th respect to an unknown distribution $D$ over $\\reals^n^$ from which we 
 can draw samples. In contrast to previous work\, we do not assume that $D$
  has finite support.\nWe design a tester that given query access to $f$\, 
 and sample access to $D$\, makes $\\poly(d/\\eps)$ many queries to $f$\, a
 ccepts with probability $1$ if $f$ is a polynomial of degree $d$\, and rej
 ects with probability at least $2/3$ if every degree-$d$ polynomial $P$ di
 sagrees with $f$ on a set of mass at least $\\eps$ with respect to $D$.\nO
 ur result also holds under mild assumptions when we receive only a polynom
 ial number of bits of precision for each query to $f$\, or when $f$ can on
 ly 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.\n \nThis is a joint work
  with Arnab Bhattacharyya\, Esty Kelman\, Noah Fleming\, and Yuichi Yoshid
 a\, and appeared in SODA’23.
LOCATION:Computer Laboratory\, William Gates Building\, FW26
END:VEVENT
END:VCALENDAR