imported>Vyalyi: Migrated current public revision from wiki.cs.hse.ru

2020-06-11T13:36:28Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

== General Information ==

Howework deadlines: each week before the lecture.

[https://docs.google.com/spreadsheets/d/1c_WexaIbhTzcRdonSRJpMTEEXj-8M2Dvg8kfGQ_t63M/edit#gid=0 Results]

[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 ==

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 16.01.20 || Анализ Фурье. Базовые определения и формулы. Тестирование линейности. || [https://www.dropbox.com/s/fablhlrr7jq25tu/prob_1.pdf?dl=0 Problem list 1 ]
|-
|| 23.01.20 || Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций. || [https://www.dropbox.com/s/8ifnldj5o8g09ep/prob_2.pdf?dl=0 Problem list 2 ]
|-
|| 30.01.20 || Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу. || [https://www.dropbox.com/s/llzb7jxxeynftef/prob_3.pdf?dl=0 Problem list 3 ]
|-
|| 06.02.20 || Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств. || [https://www.dropbox.com/s/2bxqhbgfm69u2i0/prob_4.pdf?dl=0 Problem list 4 ]
|-
|| 13.02.20 || PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром. || [https://www.dropbox.com/s/vaxc668oprirdqh/prob_5.pdf?dl=0 Problem list 5 ]

|-
|| 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]

|}

== References ==

Fourier analysis: Ryan O'Donnell [http://www.contrib.andrew.cmu.edu/~ryanod/?page_id=2334 Analysis of Boolean Functions ] 
Decision trees: [http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Survey] 
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) 
Boolean Circuits: [http://www.cs.princeton.edu/courses/archive/spr07/cos522/circuitsurvey.ps The Complexity of Finite Functions] 
Вялый М.Н. Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность. [https://www.dropbox.com/s/5qefx3j3kk3dwwz/approx-lec.pdf?dl=0 Черновик учебника.]

A Theorist's Toolkit 2019 2020 - История изменений

imported>Vyalyi: Migrated current public revision from wiki.cs.hse.ru