Разложение Фурье, ортогональный базис, скалярное произведение, расстояние между функциями,
дисперсия, ковариация, функция плотности, свертка, коэффициенты Фурье свертки. Тест на линейность (BLR-тест).
Влияние i-й координаты, дискретная производная, формула для влияния i-й координаты (в том числе монотонный случай),
чувствительность, полное влияние, среднее число голосов, которое согласуется с результатом голосования, максимум влияния для
монотонной функции. Устойчивость относительно шума, rho-связанные случайные величины, чувствительность относительно шума. Оператор шума
и формула для устойчивости. Теорема Арроу.
Модели обучения для булевых функций, сконцентрированность спектра, обучения функции у которой спектор сконцентрирован.
Спектр, сконцентрированный на степенях до k: связь с влиянием, монотонные функции, деревья принятия решений. Теорема Голдрейха-Левина
о декодировании списком кода Уолша-Адамара.
Локальное тестирование свойств булевых функций. NAE-тест и спектральные свойства функций.
Тест на диктатуру. Тест на принадлежность подмножеству диктаторов.
Тестирование свойств подмножеств. PCPP: определение, пример для множества строк нечетного веса,
для аффинного подпространства и для произвольного множества.
PCPP-сведение, PCPP-теорема, PCPP-теорема влечет PCP-теорему. Тест Хостада, формула для вероятности прохождения теста Хостада.
Тест Хостада как тест на диктатуру.
Усреднение тестов, нечетный тест Хостада. Ослабленные влияния, квазислучайность. Тест, отличающий квазислучайные функции от
диктаторов. Оценка числа координат с большим ослабленным влиянием. Задача о Unique Labeling, Unique Game Conjecture.
Построение сведения задачи Unique-Labeling к задаче MAXCSP(T) по любому тесту, отличающему квазислучайные функции от диктаторов и
использующеме предикаты из множества T.
(epsilon,k)-регулярные функции, (epsilon, k)-независимые плотности распределения.
Конструкция k-независимого распределения, использующее небольшое число случайных бит. epsilon-смещенные распределения. Конструкция
(epsilon,k)-независимого распределения на основе epsilon-смещенного.
Конструкция epsilon-смещенного распределения. Степень функций над полем F_2, степень функций у которых все ненулевые коэффициенты
Фурье соответствуют большим множествам. Теорма Виолы, доказательство первой части.
Доказательство второй части теоремы Виолы. Линейные пороговые функции, любая булевая функция, у которой коэффициенты Фурье по множествам
размера 0 и 1 совпадают с линейной пороговой, является линейной пороговой. Коэффициенты Фурье Majority, убывание k-го веса Majority.
Теорема Берри-Ессен (вариант центральной предельной теоремы), следствия. Ассимптотика влияния Majority. rho-связанные гауссианы,
вероятность того, что знак двух rho-связанных гауссианов не совпадает. Вывод ассимптотики Stab[Majority]. 2/pi-теорема, доказательство
первой части.
Разумные распределения, теорема об антиконцентрации, лемма Бонами (о разумности образа функции небольшой степени).
FKN-теорема.
(2,4)-гиперсжимаемость, (4/3, 2)-гиперсжимаемость, коэффициент расширения графа шумного гиперкуба. KKL-теорема.