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

2023-03-28T17:54:17Z

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

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

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

Recordings [11.01, 18.01, 8.02 and later]: https://disk.yandex.com/d/vxLe9CWRBRWTEg

Recordings [25.01 and 1.02]: https://disk.yandex.ru/d/fuuLQ8ZNd5VqOg

Коллоквиум пройдёт 22.03 с 14:00 онлайн: https://us06web.zoom.us/j/81449900123?pwd=d0h6MlhsT1FJdlRvQTlQRDZrME5xUT09

[https://disk.yandex.com/i/_9Jt5MswH666RQ Программа коллоквиума]

[https://docs.google.com/spreadsheets/d/1F7XMfWsl4XqzbQV6pjRpKPpHtF9ThaMG6vBTKgyMbZk/edit?usp=sharing Запись на коллоквиум]

Экзамен пройдёт 29.03 в 11.10.

Время на выполнение заданий: 90 минут. Ещё будет 10-15 минут на фотографирование и отсылку работ сюда: https://classroom.google.com/c/NjAxNTkzMzY0MjU3?cjc=awj4jj6.

[https://disk.yandex.com/i/a8DcABqKCXZnTA Демонстративный вариант]

Howework deadlines: each week before the lecture.

Link for Google Classroom: [https://classroom.google.com/c/NTQxMjgxMDAxNjQx?cjc=un6wtbj link]; code: un6wtbj

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

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

== Course Materials ==

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

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

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

|-
|| 15.02.23 || 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/dkezt5tnq1qe91u/prob_6.pdf?dl=0 Problem list 6 ]

|-
|| 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. || [https://www.dropbox.com/s/gzystpoa8hbuhob/prob_7.pdf?dl=0 Problem list 7 ]
|-
|| 1.03.23 || 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/x5nzyq523q5o8q8/prob_8.pdf?dl=0 Problem list 8 ]
|-
|| 15.03.20 || PARITY requires exponential size AC^0[3] circuit. || [https://www.dropbox.com/s/ct2j0rph361yl3c/prob_9.pdf?dl=0 Problem list 9 ]



|}

== References ==

Fourier analysis: Ryan O'Donnell [https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf 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 2022 2023 - История изменений

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