A Theorist's Toolkit 2019 2020

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

General Information

Howework deadlines: each week before the lecture.

Results

Grading

Коллоквиум состоится 3 июня, начало 10:30

Программа коллоквиума

Course Materials

Date Summary Problem list
16.01.20 Анализ Фурье. Базовые определения и формулы. Тестирование линейности. Problem list 1
23.01.20 Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций. Problem list 2
30.01.20 Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу. Problem list 3
06.02.20 Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств. Problem list 4
13.02.20 PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром. Problem list 5
19.02.20 Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Sparsity, lower and upper bounds. Problem list 6
26.02.20 Decision trees, sensitivity, block sensitivity, certificate complexity, degree. Polynomial relation between these measures. Problem list 7
04.03.20 Lower bound for approximation of OR by a polynomial. Connection between block sensitivity and degree. Chebyshev polynomials, their basic properties. Approximation of OR by a polynomial of degree $\sqrt{n}$. Problem list 8
11.03.20 PARITY requires exponential size AC^0[3] circuit. Problem list 9
08.04.20 Приближенные алгоритмы. Примеры и определения (слайды лекции).
Видео всего занятия
Задачи 10
15.04.20 Трудности с методом усреднения. ЛП релаксации (слайды лекции).

Видео всего занятия Объявление: задача 11.8 удаляется их списка задач домашнего задания и объявляется бонусной. За ее решение будет дан дополнительный бонус к оценке за домашние задания.

Задачи 11
22.04.20 Метод эллипсоидов. ЛП релаксации для MAX-SAT и MAX-CUT (слайды лекции)

Видео всего занятия

Задачи 12

29.04.20 Точность ЛП релаксации для MAX-CUT (слайды лекции с исправлением допущенных на лекции ошибок)

Видео всего занятия

Задачи 13

06.05.20 SDP релаксации (слайды лекции)

Видео всего занятия

Задачи 14

13.05.20 Точность релаксации Гёманса-Вильямсона. SDP релаксация для MAX2SAT (слайды лекции)

Видео всего занятия

Задачи 15

20.05.20 Гауссово округление (слайды лекции)

Видео всего занятия

Задачи 16

27.05.20 Иерархия Лассера (слайды лекции)

Видео всего занятия

Задачи 17

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
Вялый М.Н. Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность. Черновик учебника.