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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 25: Строка 25:
  
 
|-
 
|-
−
  || 26.01.21 || Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций. || [https://www.dropbox.com/s/bdplb2s7zohw7d0/prob_2.pdf?dl=0 Problem list 2 ] 
+
  || 26.01.21 || Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций. ||  
 
|-
 
|-
−
  || 2.02.21 || Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу. || [https://www.dropbox.com/s/2rflha7in7heq9c/prob_3.pdf?dl=0 Problem list 3 ] 
+
  || 2.02.21 || Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу. ||  
 
|-
 
|-
−
  || 9.02.21 || Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств. || [https://www.dropbox.com/s/5rhiwllsleco5e3/prob_4.pdf?dl=0 Problem list 4 ] 
+
  || 9.02.21 || Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств. ||  
 
|-
 
|-
  
  
−
  || 16.02.21 || PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром. || [https://www.dropbox.com/s/i5e9jd7tisu0w5k/prob_5.pdf?dl=0 Problem list 5 ]
+
  || 16.02.21 || PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром. ||  
  
 
|-
 
|-
−
  || 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 ]
+
  || 25.02.21 || Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Threshold degree and sparsity, lower and upper  bounds. ||  
  
  
 
|-
 
|-
−
  || 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 ] 
+
  || 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. ||  
 
|-
 
|-
−
  || 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 ] 
+
  || 09.03.21 || Connection between block sensitivity and degree. Chebyshev polynomials, their basic properties. Approximation of OR by a polynomial of degree $\sqrt{n}$. ||
  
 
|-
 
|-
−
  || 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 ] 
+
  || 11.03.20 || PARITY requires exponential size AC^0[3] circuit. ||  
 
<!--
 
<!--
 
|-
 
|-
 
  || 08.04.20 || Приближенные алгоритмы. Примеры и определения [https://www.dropbox.com/s/zm9kw9xssvvrq62/lec10.pdf?dl=0 (слайды лекции)].
 
  || 08.04.20 || Приближенные алгоритмы. Примеры и определения [https://www.dropbox.com/s/zm9kw9xssvvrq62/lec10.pdf?dl=0 (слайды лекции)].
 
  [https://www.youtube.com/watch?v=B2KgNkBN69A Видео всего занятия]
 
  [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 (слайды лекции)].
 
|| 15.04.20 || Трудности с методом усреднения. ЛП релаксации [https://www.dropbox.com/s/lpn0akpwaffygne/lec11.pdf?dl=0 (слайды лекции)].
 
[https://www.youtube.com/watch?v=0MK4IffYQfE Видео всего занятия] '''Объявление: задача 11.8 удаляется их списка задач домашнего задания и объявляется бонусной. За ее решение будет дан дополнительный бонус к оценке за домашние задания.'''
 
[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 (слайды лекции)]
 
|| 22.04.20 || Метод эллипсоидов. ЛП релаксации для MAX-SAT и MAX-CUT [https://www.dropbox.com/s/7rtyncq8xbbtm6c/lec12.pdf?dl=0 (слайды лекции)]

Версия 15:36, 11 января 2023

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 Passcode 247602


Howework deadlines: each week before the lecture.

Results

Grading

Course Materials

Date Summary Problem list
19.01.21 Анализ Фурье. Базовые определения и формулы. Тестирование линейности. Problem list 1
26.01.21 Плотности распределений, свертка. Social choice theory. Влияния, дискретные производные функций. Формулы для влияний через коэффициенты Фурье. Оценка влияний монотонных транзитивно-симметричных функций.
2.02.21 Общее влияние. Функция голосования максимизирует общее влияние среди монотонных функций. Неравенство Пуанкаре. Стабильность, чувствительность к шуму. Оператор шума. Диктаторы самые чувствительные среди сбалансированных. Теорема Эрроу.
9.02.21 Концентрация на низких степенях. Оценки через влияние и чувствительность к шуму. Индикаторы линейных и афинных подпространств, их спектр. Разрешающие деревья. Подстановка переменных. Сужения до афинных подпространств.
16.02.21 PAC-модель для равномерного распределения. Сведение изучения функции к нахождению больших коэффициентов Фурье. Изучение функций со сконцентрированным спектром.
25.02.21 Threshold functions. Chow's parameters. Concentration on degree 1. Polynomial threshold functions. Threshold degree and sparsity, lower and upper bounds.


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.
09.03.21 Connection between block sensitivity and degree. Chebyshev polynomials, their basic properties. Approximation of OR by a polynomial of degree $\sqrt{n}$.
11.03.20 PARITY requires exponential size AC^0[3] circuit.

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

Источник — «http://wiki.cs.hse.ru/index.php?title=A_Theorist%27s_Toolkit_2022_2023&oldid=75389»