BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230113T120000Z
UID:5659c614375d76d3440fe1e6e2643ba9-394
DTSTAMP:19700101T120017Z
DESCRIPTION:Low Degree Testing over the Reals
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/394/low-degree-testing-over-the-reals/
SUMMARY: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 a joint work with Arnab Bhattacharyya, Esty Kelman, Noah Fleming, and Yuichi Yoshida, and will appear in SODA23.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul
DTSTART:20230113T120000Z
END:VEVENT
END:VCALENDAR