Abstract

What global properties of a function can we infer from local information? Bernstein-type discretization inequalities offer one answer: they show the supremum norm of a polynomial can be controlled by its absolute 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 discretization with few test points. Along the way we develop a probabilistic technique for iterating one-dimensional inequalities without paying a dimension-dependent price.

As a consequence, we obtain Bohnenblust—Hille inequalities for functions on Z_k^n (or the hypergrid). Following the recent breakthrough of Eskenazis and Ivanisvili (STOC ‘22), these imply learning algorithms for low-degree functions with only log(n) random queries.

Based on a line of work with Lars Becker, Ohad Klein, Alexander Volberg, and Haonan Zhang.