A Theorist's Toolkit 2022 2023

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

General Information

Lectures: Alexey Milovanov (https://t.me/AlexeySMilovanov)

Seminars: Pavel Zakharov (https://t.me/DuckBinLaden)

Group in TG: https://t.me/+UteTaamsEgce5byt

zoom: https://us02web.zoom.us/j/87338169851?pwd=S0ZvbXBqNWhzVkJYbEtJU2dwcFNrQT09 Passcode 247602

Recordings: https://disk.yandex.com/d/vxLe9CWRBRWTEg

Howework deadlines: each week before the lecture.

Results

Grading

Course Materials

Date Summary Problem list
11.01.23 Анализ Фурье. Базовые определения и формулы. Тестирование линейности. Problem list 1
18.01.23 Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций.
25.01.23 Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу.
1.02.23 Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств.
8.02.23 PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром.
15.02.23 Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Threshold degree and sparsity, lower and upper bounds.


22.02.23 Decision trees, sensitivity, block sensitivity, certificate complexity, degree. Polynomial relation between these measures. Lower bound for approximation of OR by a polynomial.
1.03.23 Connection between block sensitivity and degree. Chebyshev polynomials, their basic properties. Approximation of OR by a polynomial of degree $\sqrt{n}$.
15.03.20 PARITY requires exponential size AC^0[3] circuit.



References

Fourier analysis: Ryan O'Donnell Analysis-Of-Boolean-Functions
Decision trees: Survey
Low degree approximation of OR: A. Klivans and R. Servedio, Toward Attribute-Efficient Learning of Decision Lists and Parities. (Section 4.2)
Boolean Circuits: The Complexity of Finite Functions