A Theorist's Toolkit 2019 2020 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия 3 участников)
Строка 7: Строка 7:
 
[https://www.dropbox.com/s/4vazj0kzmu2vaqh/grading.pdf?dl=0 Grading]
 
[https://www.dropbox.com/s/4vazj0kzmu2vaqh/grading.pdf?dl=0 Grading]
  
 +
'''Коллоквиум состоится 3 июня, начало 10:30'''
 +
 +
[https://www.dropbox.com/s/x0fiyeqwlfy0vqk/col06.pdf?dl=0 Программа коллоквиума]
  
 
== Course Materials ==
 
== Course Materials ==
Строка 25: Строка 28:
  
 
|-
 
|-
  || 20.02.20 || Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Sparsity, lower and upper  bounds. || [http://www.mi.ras.ru/~podolskii/files/toolkit/prob_7.pdf Problem list 7 ]  
+
  || 19.02.20 || Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Sparsity, lower and upper  bounds. || [https://www.dropbox.com/s/p80jsqx19oadun8/prob_6.pdf?dl=0 Problem list 6 ]  
 
|-
 
|-
 +
|| 26.02.20 || Decision trees, sensitivity, block sensitivity, certificate complexity, degree. Polynomial relation between these measures. || [https://www.dropbox.com/s/931lt5fhpvjvg0z/prob_7.pdf?dl=0 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}$. || [https://www.dropbox.com/s/i3sivtf7jxjw2wf/prob_8.pdf?dl=0 Problem list 8 ] 
 +
|-
 +
|| 11.03.20 || PARITY requires exponential size AC^0[3] circuit. || [https://www.dropbox.com/s/u7ihr99ab8vl1gv/prob_9.pdf?dl=0 Problem list 9 ] 
 +
|-
 +
|| 08.04.20 || Приближенные алгоритмы. Примеры и определения [https://www.dropbox.com/s/zm9kw9xssvvrq62/lec10.pdf?dl=0 (слайды лекции)].
 +
[https://www.youtube.com/watch?v=B2KgNkBN69A Видео всего занятия]
 +
|| [https://www.dropbox.com/s/vqy52lwmtx06vsp/pr01CA.pdf?dl=0 Задачи 10 ]
 +
|-
 +
|| 15.04.20 || Трудности с методом усреднения. ЛП релаксации [https://www.dropbox.com/s/lpn0akpwaffygne/lec11.pdf?dl=0 (слайды лекции)].
 +
[https://www.youtube.com/watch?v=0MK4IffYQfE Видео всего занятия] '''Объявление: задача 11.8 удаляется их списка задач домашнего задания и объявляется бонусной. За ее решение будет дан дополнительный бонус к оценке за домашние задания.'''
 +
|| [https://www.dropbox.com/s/lutj0lb3dj4o9q1/pr02CA.pdf?dl=0 Задачи 11 ]
 +
|-
 +
|| 22.04.20 || Метод эллипсоидов. ЛП релаксации для MAX-SAT и MAX-CUT [https://www.dropbox.com/s/7rtyncq8xbbtm6c/lec12.pdf?dl=0 (слайды лекции)]
 +
[https://youtu.be/ccJvGFT9_Nw Видео всего занятия]
 +
||
 +
[https://www.dropbox.com/s/dam4gzhmdxlloof/pr03CA.pdf?dl=0 Задачи 12]
 +
|-
 +
|| 29.04.20 || Точность ЛП релаксации для MAX-CUT [https://www.dropbox.com/s/qugnj947aux2xnx/lec13.pdf?dl=0 (слайды лекции с исправлением допущенных на лекции ошибок)]
 +
[https://www.youtube.com/watch?v=BBZFkh2yOUk Видео всего занятия]
 +
||
 +
[https://www.dropbox.com/s/y5xz54tzbxl6lrh/pr04CA.pdf?dl=0 Задачи 13]
 +
|-
 +
|| 06.05.20 || SDP релаксации [https://www.dropbox.com/s/6at7x64jtnac0v4/lec14.pdf?dl=0 (слайды лекции)]
 +
[https://www.youtube.com/watch?v=ZFpAw1daMf0 Видео всего занятия]
 +
||
 +
[https://www.dropbox.com/s/r0y9nkkjq90d4qh/pr05CA.pdf?dl=0 Задачи 14]
 +
|-
 +
|| 13.05.20 || Точность релаксации Гёманса-Вильямсона. SDP релаксация для MAX2SAT [https://www.dropbox.com/s/bco835u48r6nh13/lec15.pdf?dl=0 (слайды лекции)]
 +
[https://www.youtube.com/watch?v=NeHNjyPCMD4 Видео всего занятия]
 +
||
 +
[https://www.dropbox.com/s/apakoirup6lfrsl/pr06CA.pdf?dl=0 Задачи 15]
 +
|-
 +
|| 20.05.20 || Гауссово округление [https://www.dropbox.com/s/fstgaf4mpjcszgm/lec16.pdf?dl=0 (слайды лекции)]
 +
[https://www.youtube.com/watch?v=kDXiEKjHUX0 Видео всего занятия]
 +
||
 +
[https://www.dropbox.com/s/4e12p5r32kezau5/pr07CA.pdf?dl=0 Задачи 16]
 +
|-
 +
|| 27.05.20 || Иерархия Лассера [https://www.dropbox.com/s/9as4jpy0y4ncdd9/lec17.pdf?dl=0 (слайды лекции)]
 +
[https://www.youtube.com/watch?v=RUfpPkUJ9Q4 Видео всего занятия]
 +
||
 +
[https://www.dropbox.com/s/9jt4ss3o2xzmzt3/pr08CA.pdf?dl=0 Задачи 17]
 
<!---
 
<!---
 
  || 14.02.19 || Anti-concentration. Paley-Zygmund inequality. B-reasonability, simple properties. The Bonami Lemma. Anti-concentration of low degree polynomials. FKN Theorem. || [http://www.mi.ras.ru/~podolskii/files/toolkit/prob_6.pdf Problem list 6 ]   
 
  || 14.02.19 || Anti-concentration. Paley-Zygmund inequality. B-reasonability, simple properties. The Bonami Lemma. Anti-concentration of low degree polynomials. FKN Theorem. || [http://www.mi.ras.ru/~podolskii/files/toolkit/prob_6.pdf Problem list 6 ]   
 
|-
 
|-
 
 
  || 28.02.19 || Decision trees, sensitivity, block sensitivity, certificate complexity, degree. Polynomial relation between these measures. || [http://www.mi.ras.ru/~podolskii/files/toolkit/prob_8.pdf Problem list 8 ]   
 
  || 28.02.19 || Decision trees, sensitivity, block sensitivity, certificate complexity, degree. Polynomial relation between these measures. || [http://www.mi.ras.ru/~podolskii/files/toolkit/prob_8.pdf Problem list 8 ]   
 
|-
 
|-
Строка 43: Строка 88:
  
 
Fourier analysis: Ryan O'Donnell [http://www.contrib.andrew.cmu.edu/~ryanod/?page_id=2334 Analysis of Boolean Functions ] <br>
 
Fourier analysis: Ryan O'Donnell [http://www.contrib.andrew.cmu.edu/~ryanod/?page_id=2334 Analysis of Boolean Functions ] <br>
 +
Decision trees: [http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Survey] <br>
 +
Low degree approximation of OR: [http://www.cs.columbia.edu/~rocco/Public/d16.pdf A. Klivans and R. Servedio, Toward Attribute-Efficient Learning of Decision Lists and Parities.] (Section 4.2) <br>
 +
Boolean Circuits: [http://www.cs.princeton.edu/courses/archive/spr07/cos522/circuitsurvey.ps The Complexity of Finite Functions] <br>
 +
Вялый М.Н. Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность. [https://www.dropbox.com/s/5qefx3j3kk3dwwz/approx-lec.pdf?dl=0 Черновик учебника.] <br>

Текущая версия на 16:36, 11 июня 2020

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