https://www.wikicshse.ru/index.php?action=history&feed=atom&title=NIS-TCS-20-21NIS-TCS-20-21 - История изменений2026-06-08T05:12:56ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.wikicshse.ru/index.php?title=NIS-TCS-20-21&diff=517&oldid=previmported>Vpodolskii: Migrated current public revision from wiki.cs.hse.ru2022-06-06T10:39:28Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>== Общая информация ==<br />
<br />
<br />
Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.<br />
<br />
В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.<br />
<br />
О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в [https://t.me/joinchat/UzonA5kv5_wrhLwU канале специализации].<br />
<br />
Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 1-2 статьям. В конце модуля проводится семинар, на котором обсуждается содержание статей и возникшие вопросы, а также пишется небольшая письменная работа по статье. <br />
<br />
Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента.<br />
<br />
== Продолжительность НИС ==<br />
<br />
Курс проходит в следующих модулях <br><br />
3 курс ПМИ: 1-4 модули <br><br />
4 курс ПМИ: 1-3 модули <br><br />
1 курс НОД: 1-4 модули <br><br />
2 курс НОД: 1-2 модули<br />
<br />
== Статьи для разбора ==<br />
<br />
<b>3 модуль.</b> Локальная лемма Ловаса. Требуется прочитать и разобрать [https://arxiv.org/abs/0903.0544 статью Мозера, Тардоша], а также раздел 6 в [https://arxiv.org/abs/1305.1535 тексте Румянцева, Шеня]. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей.<br />
<br />
Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30.<br />
<br />
<b>4 модуль.</b> Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части: <br><br />
<ol><br />
<li>нижняя оценка степени булевой функции через блочную чувствительность, </li><br />
<li>связь чувствительности с максимальной степенью подграфа булева куба, </li><br />
<li>нижняя оценка максимальной степени подграфа булева куба.</li><br />
</ol><br />
Первое — это довольно старый и известный результат Nisan, второе — также довольно старый результат Gotsman и Linial. Третье — это результат Huang 2019 года, который собственно и позволил доказать гипотезу. <br><br />
В рамках НИС требуется разобраться с доказательством гипотезы. Для этого есть целый ряд возможных источников.<br />
<ul><br />
<li>Есть оригинальные статьи [https://www.sciencedirect.com/science/article/pii/0097316592900608 Gotsman, Linial] и [https://arxiv.org/abs/1907.00847 Huang].</li><br />
<li>Есть полное изложение всего доказательства в [https://terrytao.wordpress.com/2019/07/26/twisted-convolution-and-the-sensitivity-conjecture/ блоге Tao].</li><br />
<li>Часть 2 хорошо описана в разделе 5.6 этого [https://theoryofcomputing.org/articles/gs004/ обзора].</li><br />
<li>Есть альтернативное доказательство части 3 [https://www.cs.stanford.edu/~knuth/papers/huang.pdf by Knuth].</li><br />
<li>Еще одно альтернативное доказательство части 3 есть в [https://fedyapetrov.wordpress.com/2019/07/03/low-level-variant-of-huangs-argument-for-sensitivity-conjecture/ блоге Федора Петрова].</li><br />
<li>Еще одно альтернативное доказательство части 3 есть в [https://arxiv.org/abs/1907.11175 заметке Романа Карасева].</li><br />
<li>Еще одно полное изложение доказательства есть в этом (кажется, студенческом) [https://www.ams.org/journals/bull/2020-57-04/S0273-0979-2020-01697-6/ обзоре]. </li><br />
</ul><br />
<br />
Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС).<br />
<br />
Семинар с обсуждением статьи и тестом пройдет 14 июня с 16:20 до 17:40.<br />
<br />
== Правила оценивания ==<br />
<br />
Вес посещения мероприятий в итоговой оценке составляет 30%, разбора статей — 40%, экзамена — 30%.<br />
<br />
Оценка за разбор статей выставляется на основании письменных работ.</div>imported>Vpodolskii