Learning Low-Degree Functions on the Discrete Hypercube

Explore the fundamental problem of reconstructing unknown functions on the n-dimensional discrete hypercube in this mathematics colloquium talk. Delve into the random query model and discover a newly found connection with polynomial inequalities dating back to Littlewood's work in 1930. Examine how this connection leads to sharper estimates for query complexity, exponentially improving upon the classical Low-Degree Algorithm of Linial, Mansour, and Nisan. Learn about the potential information-theoretic lower bound that matches these improved estimates. Gain insights into computational learning theory and its intersection with polynomial inequalities through this presentation by Alexandros Eskenazis from CNRS, Sorbonne Université.