NIS-TCS-20-21 — различия между версиями
(не показана одна промежуточная версия этого же участника) | |||
Строка 22: | Строка 22: | ||
== Статьи для разбора == | == Статьи для разбора == | ||
− | 3 модуль. Локальная лемма Ловаса. Требуется прочитать и разобрать [https://arxiv.org/abs/0903.0544 статью Мозера, Тардоша], а также раздел 6 в [https://arxiv.org/abs/1305.1535 тексте Румянцева, Шеня]. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей. | + | <b>3 модуль.</b> Локальная лемма Ловаса. Требуется прочитать и разобрать [https://arxiv.org/abs/0903.0544 статью Мозера, Тардоша], а также раздел 6 в [https://arxiv.org/abs/1305.1535 тексте Румянцева, Шеня]. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей. |
Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30. | Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30. | ||
+ | |||
+ | <b>4 модуль.</b> Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части: <br> | ||
+ | <ol> | ||
+ | <li>нижняя оценка степени булевой функции через блочную чувствительность, </li> | ||
+ | <li>связь чувствительности с максимальной степенью подграфа булева куба, </li> | ||
+ | <li>нижняя оценка максимальной степени подграфа булева куба.</li> | ||
+ | </ol> | ||
+ | Первое — это довольно старый и известный результат Nisan, второе — также довольно старый результат Gotsman и Linial. Третье — это результат Huang 2019 года, который собственно и позволил доказать гипотезу. <br> | ||
+ | В рамках НИС требуется разобраться с доказательством гипотезы. Для этого есть целый ряд возможных источников. | ||
+ | <ul> | ||
+ | <li>Есть оригинальные статьи [https://www.sciencedirect.com/science/article/pii/0097316592900608 Gotsman, Linial] и [https://arxiv.org/abs/1907.00847 Huang].</li> | ||
+ | <li>Есть полное изложение всего доказательства в [https://terrytao.wordpress.com/2019/07/26/twisted-convolution-and-the-sensitivity-conjecture/ блоге Tao].</li> | ||
+ | <li>Часть 2 хорошо описана в разделе 5.6 этого [https://theoryofcomputing.org/articles/gs004/ обзора].</li> | ||
+ | <li>Есть альтернативное доказательство части 3 [https://www.cs.stanford.edu/~knuth/papers/huang.pdf by Knuth].</li> | ||
+ | <li>Еще одно альтернативное доказательство части 3 есть в [https://fedyapetrov.wordpress.com/2019/07/03/low-level-variant-of-huangs-argument-for-sensitivity-conjecture/ блоге Федора Петрова].</li> | ||
+ | <li>Еще одно альтернативное доказательство части 3 есть в [https://arxiv.org/abs/1907.11175 заметке Романа Карасева].</li> | ||
+ | <li>Еще одно полное изложение доказательства есть в этом (кажется, студенческом) [https://www.ams.org/journals/bull/2020-57-04/S0273-0979-2020-01697-6/ обзоре]. </li> | ||
+ | </ul> | ||
+ | |||
+ | Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС). | ||
+ | |||
+ | Семинар с обсуждением статьи и тестом пройдет 14 июня с 16:20 до 17:40. | ||
== Правила оценивания == | == Правила оценивания == |
Текущая версия на 13:39, 6 июня 2022
Общая информация
Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.
В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.
О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в канале специализации.
Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 1-2 статьям. В конце модуля проводится семинар, на котором обсуждается содержание статей и возникшие вопросы, а также пишется небольшая письменная работа по статье.
Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента.
Продолжительность НИС
Курс проходит в следующих модулях
3 курс ПМИ: 1-4 модули
4 курс ПМИ: 1-3 модули
1 курс НОД: 1-4 модули
2 курс НОД: 1-2 модули
Статьи для разбора
3 модуль. Локальная лемма Ловаса. Требуется прочитать и разобрать статью Мозера, Тардоша, а также раздел 6 в тексте Румянцева, Шеня. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей.
Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30.
4 модуль. Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части:
- нижняя оценка степени булевой функции через блочную чувствительность,
- связь чувствительности с максимальной степенью подграфа булева куба,
- нижняя оценка максимальной степени подграфа булева куба.
Первое — это довольно старый и известный результат Nisan, второе — также довольно старый результат Gotsman и Linial. Третье — это результат Huang 2019 года, который собственно и позволил доказать гипотезу.
В рамках НИС требуется разобраться с доказательством гипотезы. Для этого есть целый ряд возможных источников.
- Есть оригинальные статьи Gotsman, Linial и Huang.
- Есть полное изложение всего доказательства в блоге Tao.
- Часть 2 хорошо описана в разделе 5.6 этого обзора.
- Есть альтернативное доказательство части 3 by Knuth.
- Еще одно альтернативное доказательство части 3 есть в блоге Федора Петрова.
- Еще одно альтернативное доказательство части 3 есть в заметке Романа Карасева.
- Еще одно полное изложение доказательства есть в этом (кажется, студенческом) обзоре.
Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС).
Семинар с обсуждением статьи и тестом пройдет 14 июня с 16:20 до 17:40.
Правила оценивания
Вес посещения мероприятий в итоговой оценке составляет 30%, разбора статей — 40%, экзамена — 30%.
Оценка за разбор статей выставляется на основании письменных работ.