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

2021-06-21T21:52:04Z

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

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

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

[https://docs.google.com/spreadsheets/d/1julKVsk7_qMqQzlQ9PE4xbZsl-JdEKn-1xa-5HiVhEs/edit?usp=sharing Запись на экзамен]

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

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

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

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

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

[https://docs.google.com/spreadsheets/d/16OKZ92DWL64X6vc3eT24nHzhIIMp99GwbRhtGmGHzvo/edit?usp=sharing Оценки]

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

====Семинар 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

====Семинар 6 (29 октября). ====
Введение в Property testing
https://www.hse.ru/mirror/pubs/share/182501491

====Семинар 7 (5 ноября). ====
https://drive.google.com/file/d/11Emea-Lf1C6wtyIDFw-Hk3gQwfubyhAl/view?usp=sharing

====Семинар 8 (12 ноября). ====
https://drive.google.com/file/d/11Emea-Lf1C6wtyIDFw-Hk3gQwfubyhAl/view?usp=sharing

====Семинар 9 (19 ноября). ====
https://drive.google.com/file/d/1FDoTGOFyuZXKosvo7WtFg0umlHbJ00OL/view?usp=sharing

====Семинар 10 (26 ноября). ====
https://www.dropbox.com/s/xr27ls89kfbwlwa/cw17.pdf?dl=0

====Семинар 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

Project Seminar 2020 2021 - История изменений

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