Low-degree learning and the metric entropy of polynomials

Alexandros Eskenazis, Paata Ivanisvili, Lauritz Streck

Let ${\mathcal{F}}_{n,d}$ be the class of all functions $f:\{-1,1{\}}^n\to [-1,1]$ on the $n$-dimensional discrete hypercube of degree at most $d$. In the first part of this paper, we p…