Приближение булевых функций многочленами

Подход, использующий приближение булевых функций $f\colon\{0,1\}^n\to\{0,1\}$ многочленами для получения результатов о вычислительной сложности булевых функции, применяется с 60-х годов, и с тех пор с его помощью было получено множество интересных результатов. В разных приложениях используются разные виды многочленов (многочлены над действительными числами, многочлены над конечными полями). Приближение также рассматривается в разных смыслах (по норме $l_1$; доля точек несовпадения значения функции и значения многочлена; приближение знаком многочлена). В этом докладе мы обсудим несколько таких моделей и их приложения.