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é.

Learning low-degree functions on the discrete hypercube - Alexandros Eskenazis