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

2021-03-16T16:31:20Z

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

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

== General Information ==

Howework deadlines: each week before the lecture.

[https://docs.google.com/spreadsheets/d/1xzsdIKszkxgnmaudG9OZ14NGRWJSjln-V2vZ5uWsnL8/edit?usp=sharing Results]

[https://www.dropbox.com/s/ctxqn92alz57wng/grading.pdf?dl=0 Grading]

'''Коллоквиум состоится 23 марта, начало в 18:10'''

[https://www.dropbox.com/s/i3rrctasla2m2j1/col.pdf?dl=0 Программа коллоквиума]

= Seminars =

[https://jamboard.google.com/d/1KddkDWduG05VvOVPH2vmWJQTyVIYXTkSBcF0PdhFrwY/edit?usp=sharing Seminar 1]

[https://jamboard.google.com/d/1GUJxb9RPXj-0ibmOe4R8bjmObTlMsxMrS1ZLuPP0sVE/edit?usp=sharing Seminar 2]

[https://jamboard.google.com/d/1R28n0-HYIGdIcqXDpoVBIZVtR1ozrJbgWFoJTIRgINk/edit?usp=sharing Seminar 3]

[https://jamboard.google.com/d/1PTswMYle8wfIPsPtCANL-ED4Jx1mfaD2b6QYfAYYQEI/edit?usp=sharing Seminar 4]

[https://jamboard.google.com/d/17biK34LL0y7DpAkFp3WxHQ7gpKSk6Edx1WmHvfRrWP0/edit?usp=sharing Seminar 5]

[https://jamboard.google.com/d/12B11tpRAQdHqMyLvvKle0mCLP_76-3tUYJjT9tfM8js/edit?usp=sharing Seminar 6]

[https://jamboard.google.com/d/1dOm-uqXsczh4OVtIkt6w1zRHj-XD7m7Ioe0bshetKsA/edit?usp=sharing Seminar 7]

[https://jamboard.google.com/d/1JpQrwpyP8z4-U5i2E4lakHFTRIvqgMVSn0SDysZi-yA/edit?usp=sharing Seminar 8]

[https://jamboard.google.com/d/1plB4LvjrN3qdHAboKpObI7U7TkZXIG4n_dKufeJkYHU/edit?usp=sharing Seminar 9]


== Course Materials ==

[https://www.dropbox.com/s/b0rp3jjo60bshpz/scribes.pdf?dl=0 Записи с планшета с лекций] (New!)

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 19.01.21 || Анализ Фурье. Базовые определения и формулы. Тестирование линейности. || [https://www.dropbox.com/s/9tdb1j7wwnywsdp/prob_1.pdf?dl=0 Problem list 1 ]

|-
|| 26.01.21 || Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций. || [https://www.dropbox.com/s/bdplb2s7zohw7d0/prob_2.pdf?dl=0 Problem list 2 ]
|-
|| 2.02.21 || Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу. || [https://www.dropbox.com/s/2rflha7in7heq9c/prob_3.pdf?dl=0 Problem list 3 ]
|-
|| 9.02.21 || Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств. || [https://www.dropbox.com/s/5rhiwllsleco5e3/prob_4.pdf?dl=0 Problem list 4 ]
|-

|| 16.02.21 || PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром. || [https://www.dropbox.com/s/i5e9jd7tisu0w5k/prob_5.pdf?dl=0 Problem list 5 ]

|-
|| 25.02.21 || Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Threshold degree and sparsity, lower and upper bounds. || [https://www.dropbox.com/s/bglyodp1kuetwni/prob_6.pdf?dl=0 Problem list 6 ]

|-
|| 02.03.21 || Decision trees, sensitivity, block sensitivity, certificate complexity, degree. Polynomial relation between these measures. Lower bound for approximation of OR by a polynomial. || [https://www.dropbox.com/s/c838g7sd8vacwln/prob_7.pdf?dl=0 Problem list 7 ]
|-
|| 09.03.21 || 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/wk6ms4c88m9jgps/prob_8.pdf?dl=0 Problem list 8 ]

|-
|| 11.03.20 || PARITY requires exponential size AC^0[3] circuit. || [https://www.dropbox.com/s/kgz29tyy7964ss2/prob_9.pdf?dl=0 Problem list 9 ]


|}

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

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

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