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

2023-05-17T14:03:48Z

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

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

== Общая информация ==

Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.

В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.

О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в [https://t.me/joinchat/UzonA5kv5_wrhLwU канале специализации].

Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 1-2 статьям. В конце модуля проводится семинар, на котором обсуждается содержание статей и возникшие вопросы, а также пишется небольшая письменная работа по статье.

Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента.

== Продолжительность НИС ==

Курс проходит в следующих модулях 
3 курс ПМИ: 1-4 модули 
4 курс ПМИ: 1-3 модули 
1 курс НОД: 1-4 модули 
2 курс НОД: 1-2 модули

== Статьи для разбора ==

1 модуль. PIT. Требуется прочитать обзор [https://eccc.weizmann.ac.il/report/2009/101/ Saxena, Progress on Polynomial Identity Testing]
Подробно нужно разобрать разделы 1-3. Из остальных разделов важно уяснить формулировки результатов и основные идеи доказательств, без технических подробностей.

Семинар с обсуждением статьи и тестом пройдет 15 октября (суббота), 13:00-14:20 [https://us02web.zoom.us/j/81175340332?pwd=ZFJqMGdQRGR2Rk5YSzM3cWdJcHFKQT09 Ссылка на zoom для этого семинара]

2 модуль. Требуется разобрать статью [https://www.cs.dartmouth.edu/~ac/Pubs/focs01-infocomplex.pdf Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao: Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity].

Семинар с обсуждением статьи и тестом пройдет в два занятия (посетить нужно одно из них, они равноценные). Даты, время и ссылка на зум:
# 03.12 (суббота), 13:00-14:20, [https://us02web.zoom.us/j/86243036669?pwd=djhCRFBuVmd3TklxY3ZwUzF6L0JSdz09 ссылка], пароль: 121768
# 05.12 (понедельник), 11:30 - 12:50, [https://us02web.zoom.us/j/87212136870?pwd=VUw5VU1oZVBsaGJvVjB5QmZwK0p2QT09 ссылка], пароль 611965

Ознакомиться с понятием энтропии можно здесь
[https://www.dropbox.com/s/wf05hwmzbjaelrr/main.pdf?dl=0 Конспекты лекций по теории информации.]

3 модуль. Основное задание: разобрать статью [https://arxiv.org/abs/2211.09055 J. Gilmer A constant lower bound for the union-closed sets conjecture]. В ней сделано неожиданное продвижение в решении знаменитой гипотезы Франкла в экстремальной комбинаторике. Результат слабее основной гипотезы, но намного сильнее всего известного до тех пор.

Дополнительные необязательные предложения.
# Статья Гилмера вызвала большой интерес, появилось сразу несколько усилений результата Гилмера (arXiv:2212.12500 arXiv:2212.00658 arXiv:2211.13139 arXiv:2211.11731 arXiv:2211.11689 arXiv:2211.11504) и опровержений некоторых его надежд на полное решение гипотезы Франкла (arXiv:2211.12401 ). Рекомендуется посмотреть на эти статьи, чтобы получить представление о текущем состоянии дел.
# Интересно также упростить доказательство Гилмера ценой ухудшения константы. Если у кого-то такое получится, дайте знать: это интересно многим!

Семинар с обсуждением статьи и тестом пройдет 25.02 (суббота), 13:00-14:20, [ https://us02web.zoom.us/j/81089815250?pwd=YUlDSjVQdmJBS0hhbktNVzN3bVdPZz09 ссылка], пароль: 331217

Занятие, как обычно, закончится тестом на 20 минут. Сдавать тест нужно в [https://classroom.google.com/u/0/c/NTU2NjQ3NTExOTA1 гугл классе] (код курса ocd43fw). Просьба заранее зарегистрироваться тем, кто еще не.

4 модуль. Основное задание: разобрать по статье [https://arxiv.org/abs/1802.08876 H.Dell, M. Grohe, G. Rattan, Lovász Meets Weisfeiler and Leman] разделяющие свойства гомоморфизмов деревьев, путей, циклов в графы и их связь с другими инвариантами изоморфизма (Th.1, 2, Proposition 9, обратите внимание, что часть доказательств в аппендиксе после списка литературы).
В Th.1 формулируется также теорема Тинхофера (пункт iii). Ее доказательство не входит в основное задание.

Любителям комбинаторики дополнительно можно изучить статьи Ловаса и Тинхофера (18, 23 в списке литературы исходной статьи, доступны в электронных ресурсах библиотеки ВШЭ). Судя по текстам, доказательства не слишком трудные, но изложение не слишком reader friendly (мягко говоря). Если кто-то разберется с этими доказательствами, можно будет отдельно заслушать рассказ(-ы) по каждому из них (и такой рассказ будет приравниваться к докладу на семинаре в нашей таблице достижений). Возможно, где-то в сети есть удачные изложения этих теорем. Кто найдет и расскажет - тоже хорошо.

Семинар с обсуждением статьи и тестом пройдет 22.05 (понедельник), начало 11:00. Ссылка на zoom встречу 22.05 https://us02web.zoom.us/j/82210651050?pwd=aUUyckFFOWd3cExxQUpabXZ5LzlhUT09
пароль: 671925

== Правила оценивания ==

Вес посещения мероприятий в итоговой оценке составляет 30%, разбора статей — 40%, экзамена — 30%.

Оценка за разбор статей выставляется на основании письменных работ.

NIS-TCS-22-23 - История изменений

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