Восстановление многочленов на булевом кубе по значениям в точках. Семинар 3

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