О приближении булевых функций вещественными полиномами малой степени

Задачи приближённого представления булевых функций вещественными полиномами имеют многочисленные приложения в теории сложности вычисления и теории машинного обучения. В настоящем докладе мы рассматриваем следующую универсальную постановку, обобщающую многие известные модели: какова максимально возможная доля точек булева куба, на которых данная булева функция может точно согласовываться с вещественными полиномами данной степени? Основной результат состоит в том, что для функции сложения по модулю 2 и полиномов степени (1/2)log log n ответ в точности равен 1/2. Ядром нашего доказательства служит комбинаторный вариант известной теоремы Costello-Tao-Vu о значительном отклонении, который, по-видимому, представляет независимый интерес.
Совместная работа с E. Viola (Northeastern University).