Project Seminar 2020 2021

Содержание

1 Экзамен
2 Правила оценивания
3 Проведённые семинары
4 Предлагаемые статьи для рассказа на семинаре
5 Преподаватели

Экзамен

Экзамен пройдёт 26.06 в 10.00 в Google Meet: meet.google.com/rqm-rjdm-pqv

Запись на экзамен

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

Итоговая оценка (О_и) получается из оценки за семестр (О_с) и оценки за экзамен (О_э) по следующей формуле

O_и = 0,6 * О_с + 0,4 * О_э. Далее полученное число округляется по обычным правилам.

Оценка за семестр ставится за сделанные доклады, посещение и работу на семинарах.

На экзамене нужно рассказать о любых двух докладах (кроме рассказанных самим студентом).

Оценки

Проведённые семинары

Семинар 1 (17 сентября).

Задача равенства нулю многочлена. Лемма Шварца-Зиппеля. Применение PIT для нахождения паросочетаний.

Семинар 2 (24 сентября).

Доклад Дмитрия Правоторова о статье "Truth, justice, and cake cutting" (Chen et al., 2013). В статье приводится описание двух алгоритмов разрезания торта, удволетворяющих некоторым свойствам справедливости.

Семинар 3 (1 октября).

Введение в алгоритмическую статистику

Семинар 4 (8 октября).

Дерондомизация PIT для схем глубины 3.

Семинар 5 (15 октября).

Доклад Дмитрия Правоторова о Gibbard-Satterthwaite Theorem (любая система голосования обладает какием-то "плохим" свойством), а также о популярных способах голосования, уязвимых для манипуляций. https://drive.google.com/file/d/1pNegxQGoTCVmzEkoBjt5Bg4vgU-vDN3D/view?usp=sharing

Семинар 11 (3 декабря).

Введение в Fined-Grained complexity

http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf

Семинар 12 (10 декабря).

Доклад Александра Панаетова о числах Рамсея. https://drive.google.com/file/d/1siai9QaAR5bfEamtkN4P1UR2B_cp_VZW/view?usp=sharing

Семинар 13 (17 декабря).

Доклад Павла Корозевцева о кодах, исправляющих ошибки.

https://drive.google.com/file/d/1-rfWfmNp09JkEFewzQ00zxnYkDjO0wr8/view?usp=sharing

Семинар 14 (14 января).

https://drive.google.com/file/d/1aEX5bNfmTqJC3R3fxULvTc0uEASshK0c/view?usp=sharing

Семинар 15 (21 января).

https://drive.google.com/file/d/1t9yetCm6Cy3Vl5XXMN-HVLXzIZPfWqrg/view?usp=sharing

Семинар 16 (28 января).

https://drive.google.com/file/d/1t9yetCm6Cy3Vl5XXMN-HVLXzIZPfWqrg/view?usp=sharing

Семинар 17 (4 февраля).

https://drive.google.com/file/d/1nI6xYAjjM8v9hdAqXRcTZFfmDiJcjRnV/view?usp=sharing

Семинар 18 (11 февраля).

Доклад Андрея Недолужко о Пфаффианах.

https://drive.google.com/file/d/1023IMfVawOY0TGJOe2WYg5oVaM8Vuzit/view?usp=sharing

Семинар 19 (18 февраля).

Доклад Дмитрия Правоторова про некоторые онлайн аукционы, гарантирующие почти оптимальную прибыль.

https://drive.google.com/file/d/1023IMfVawOY0TGJOe2WYg5oVaM8Vuzit/view?usp=sharing

Семинар 20 (25 февраля).

Доклад Никиты Лукьяненко про задачу о расписании.

https://drive.google.com/file/d/1R_3KLBrtRfUB3_wHv_NYFBqG8gDKmV9W/view?usp=sharing

Семинар 21 (4 марта).

Доклад Павла Захарова: Краткий экскурс в историю случайных графов, основные модели и определения. Далее предлагается подробно остановиться на биномиальной модели G(n, p) и разобраться с несколькими теоремами про "эволюцию" -- область, изучающую всё, что связано с компонентами случайного графа: их количество, размер и сложность.

https://drive.google.com/file/d/1tXoNmzLSukdF42GNRI2jCVFR34sOVtAK/view?usp=sharing

Семинар 22 (18 марта).

Доклад Азата Султанова.

https://drive.google.com/file/d/1dMPNjtOtdg2txzo43VdJyWc7YUeU8xn-/view?usp=sharing

Семинар 23 (25 марта).

Доклад Антона Гнатенко:

Конечные автоматы -- слабая, но простая для анализа и удобная для использования в алгоритмах модель вычислений. Грубо говоря, конечный автомат -- это машина Тьюринга, у которой отобрали ленту. Автоматы традиционно используются для распознавания и преобразования слов, но их можно обобщить и на более сложные структуры. Мы рассмотрим два вида автоматов, работающих с деревьями: традиционные и хорошо изученные древесные автоматы и менее известные древоходные автоматы. Постараемся разобраться в интересной теореме: детерминированные древоходные автоматы слабее недетерминированных (нечасто встречающееся в теории автоматов явление)

https://drive.google.com/file/d/1FPkkOURB2gN5hjYbGvl74U_6yWU8LsvZ/view?usp=sharing

Семинар 24 (8 апреля).

Доклад Павла Захарова: Павел Захаров. Анонс:

Максимальный разрез в случайном гиперграфе -- явно некая случайная величина. Давайте посмотрим на случай p = cn/binom(n, k). Можно показать, что: max-q-cut(H(n, p, k)) / n сходится по вероятности к константе gamma(c, k, q). Установление этого факта не даёт никаких оценок на предельную величину, так что мы ещё приведем две оценки, представимые в виде: A_{k, q} * c + B_{k, q} * √c + o(√c), где A_{k, q} вычислена точно, а на B_{k, q} даны верхняя и нижняя оценки с зазором порядка √k.

https://drive.google.com/file/d/1eUjAjyzc0ENuuu88B9t8ZpRNjRJs_9Kj/view?usp=sharing

Семинар 25 (15 апреля).

https://drive.google.com/file/d/1lFd7APQw2y0i7PxFhfhgnNPKbjgMuqhC/view?usp=sharing

Семинар 26 (22 апреля).

Коды Адамара

Семинар 27 (3 июня).

Доклад Григория Резникова. Анонс: За более чем полвека развития теоретической информатики наука столкнулась с множеством задач, для которых не было получено алгоритмов значительно оптимальнее наивных. К таким задачам относится, например, задача поиска кратчайших расстояний между всеми парами вершин в графе, для которой полученный почти 60 лет назад алгоритм Флойда-Уоршелла остаётся одним из наиболее оптимальных. Отсутствие прогресса в подобных задачах привело к бурному развитию в последние десятилетия новой области теории сложности -- fine-grained complexity, которая ставит одной из своих целей изучение взаимосвязей гипотез о трудности тех или иных задач.

В рамках доклада мы рассмотрим недетерминированную строгую гипотезу экспоненциального времени (NSETH), которая, имея крайне естественную формулировку, обладает весьма интересными свойствами. В предположении NSETH не существует (детерминированных) сведений между определёнными задачами, что приводит к невозможности построения импликаций между гипотезами об их трудности. Из отрицания же данной гипотезы следуют нетривиальные нижние оценки на схемную сложность функций, что показывает сложность её опровержения.

Доклад основывается на работе "Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility". https://drive.google.com/file/d/1OyBZEhlh_B8aRHE380jvm1djEzPBHiVT/view?usp=sharing

Предлагаемые статьи для рассказа на семинаре

1) Nitin Saxena, Progress on Polynomial Identity Testing https://eccc.weizmann.ac.il/report/2009/101/

2) Лекции Стэндфордского университета о PIT и совершенных паросочетаниях. https://cs.stanford.edu/~mpkim/notes/lec5.pdf

Преподаватели

Милованов Алексей, almas239@gmail.com