City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Sublinear alhorithms
Saint Petersburg / autumn 2016, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Долгое время считалось, что алгоритм с линейным временем работы является естественным пределом мечтаний для любой нетривиальной вычислительной задачи. Действительно, сложно представить ситуацию, когда алгоритм не должен читать весь свой вход для ответа на поставленную задачу. Однако, современный мир и растущие объемы данных ставят более амбициозные цели: решить задачу, прочитав лишь малую долю входа. Для некоторых задач известны точные алгоритмы с сублинейным временем работы, но зачастую для естественных задач алгоритмам требуется использовать случайные биты для в некотором смысле приближенного ответа на задачу. Данная область активно развивается, и границы таких алгоритмов пока остаются размытыми. Для создания сублинейных алгоритмов используется множество интересных комбинаторных и алгебраических техник. Для многих задач найдены оптимальные алгоритмы (в некоторых гарантиях), но ещё больше остается открытых задач как в доказательстве нижних оценок, так и в улучшении верхних оценок. Область связана со многими разделами теоретической информатики: коды исправляющие ошибки, потоковые алгоритмы, коммуникационная сложность, приближенные алгоритмы, вероятностно проверяемые доказательства.

В течение семинара планируется разобрать техники и основные результаты в данной области, полученные за последние годы. Формат семинара предполагает еженедельные доклады и обсуждение материала, доклады будут делаться студентами-участниками семинара. Предполагается, что участники будут знакомы с дискретной теорией вероятностей и базовым курсом алгоритмов.

Семинар входит в магистерскую программу теоретическая информатика Академического университета.

Date and time Class|Name Venue|short Materials
16 September
19:00–20:20
Введение (Николай Карпов), Lecture ПОМИ РАН, аудитория 106 No
23 September
19:00–20:20
Тестирование на монотонность (Артур Рязанов), Lecture ПОМИ РАН, аудитория 106 No
30 September
19:00–20:20
Тестирование на монотонность 2 (Александр Логунов), Lecture ПОМИ РАН, аудитория 106 No
07 October
19:00–20:20
Тестирование на линейность и многочлены ограниченной степени (Петр Смирнов), Lecture ПОМИ РАН, аудитория 106 No
14 October
19:00–20:20
Методы доказательства нижних оценок на число запросов (Людмила Глинских), Lecture ПОМИ РАН, аудитория 106 No
21 October
19:00–20:20
Еще про нижние оценки на количество запросов (Олег Вайнзихер), Lecture ПОМИ РАН, аудитория 106 No
28 October
19:00–20:20
Тестирование свойств графа в модели плотных графов (Святослав Грязнов), Lecture ПОМИ РАН, аудитория 106 No
11 November
19:00–20:20
Обзор поточных алгоритмов (Всеволод Опарин), Lecture ПОМИ РАН, аудитория 106 No
18 November
19:00–20:20
Графы ограниченной степени и тестирование их свойств (Надежда Воронова), Lecture ПОМИ РАН, аудитория 106 No
25 November
19:00–20:20
Поиск паросочетания в регулярных двудольных графах (Николай Карпов), Lecture ПОМИ РАН, аудитория 106 No
02 December
19:00–20:20
Тестирование свойств распределений (Кирилл Симонов), Lecture ПОМИ РАН, аудитория 106 No
09 December
19:00–20:20
L_p-тестирование (Марсель Матдинов), Lecture ПОМИ РАН, аудитория 106 No
16 December
19:00–20:20
Spot-Checkers (Никита Гаевой), Lecture ПОМИ РАН, аудитория 106 No