Аннотация:
Предположим, что задан многочлен $f$ степени $d$, определённый на булевом
кубе $\{-1, 1\}^n$. Пусть также известны его значения $f(x_1),..., f(x_N)$ в
некоторых точках $x_1,..., x_N$ куба, и известно, что все значения
многочлена ограничены, например, лежат на отрезке $[-1, 1]$. Возникает
естественный вопрос: сколько таких значений достаточно, чтобы
восстановить сам многочлен с малой погрешностью? Более конкретно, нас
будет интересовать, как зависит необходимое число точек наблюдения от
размерности $n$ булева куба. В рамках курса мы дадим формальное
математическое описание этой задачи, а также рассмотрим вероятностные
подходы к задаче восстановления таких многочленов по их значениям в
отдельных точках булева куба. Нашим основным помощником будет так
называемое неравенство Боненбласта—Хилле (Bohnenblust—Hille
inequality), которое связывает норму коэффициентов многочлена с его
максимумом.
Полезным (хотя и не обязательным) будет базовое
знакомство с основами теории вероятностей и анализа.
