BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Learning low-degree functions from few random queries - Alexandros
  Eskenazis (Cambridge)
DTSTART:20211102T153000Z
DTEND:20211102T163000Z
UID:TALK165070@talks.cam.ac.uk
CONTACT:Perla Sousi
DESCRIPTION:Let f be an unknown function on the n-dimensional discrete hyp
 ercube. How many values of f do we need in order to approximately reconstr
 uct the function? In this talk we shall discuss the random query model for
  this fundamental problem from computational learning theory. We will expl
 ain a newly discovered connection with a family of polynomial inequalities
  going back to Littlewood (1930) which will in turn allow us to derive sha
 rper estimates for the query complexity of this model\, exponentially impr
 oving those which follow from the classical Low-Degree Algorithm of Linial
 \, Mansour and Nisan (1989). Based on joint work with Paata Ivanisvili (UC
  Irvine).
LOCATION:MR12  Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR