BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Dimension-free discretization inequalities with applications to lo
 w-degree learning - Joseph Slote (Caltech)
DTSTART:20241126T130000Z
DTEND:20241126T140000Z
UID:TALK224842@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:What global properties of a function can we infer from local i
 nformation? Bernstein-type discretization inequalities offer one answer: t
 hey show the supremum norm of a polynomial can be controlled by its absolu
 te maximum on a finite subset of the domain. While such inequalities enjoy
  widespread use in analysis and approximation theory\, their multivariate 
 versions are often limited by dependence on dimension or the need for very
  many test points. In this talk we show how to get a dimension-free discre
 tization with few test points. Along the way we develop a probabilistic te
 chnique for iterating one-dimensional inequalities without paying a dimens
 ion-dependent price.\n\nAs a consequence\, we obtain Bohnenblust--Hille in
 equalities for functions on Z_k^n (or the hypergrid). Following the recent
  breakthrough of Eskenazis and Ivanisvili (STOC '22)\, these imply learnin
 g algorithms for low-degree functions with only log(n) random queries.\n\n
 Based on a line of work with Lars Becker\, Ohad Klein\, Alexander Volberg\
 , and Haonan Zhang.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR