Low Degree Testing over the Reals

on YouTube ↗33m

" summary

Gives a distribution-free local tester that decides whether a function R^n → R has total degree ≤ d with query complexity independent of n (depends on d and ε) by reducing to line restrictions and a d+2-point consistency check, building a self-corrected degree-d polynomial via random directions inside a small Gaussian-concentrated ball, and extending by interpolation; handles discrete lattices using lattice-crypto tools, proves a stability lemma via Chebyshev extremal bounds.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 1:34Motivation for low degree testing
3. 4:09Property testing over real functions
4. 9:51Exact testing with real RAM
5. 14:12Self-correcting and test approach
6. 22:35Proving tester for degree d
7. 24:48Local to global lemma
8. 28:45Induction proof for dimension n
9. 30:15Stability lemma for approximate testing
10. 31:44Open questions