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

Expanders and Their Applications
Saint Petersburg / spring 2017, посмотреть все семестры

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

Экспандеры (расширяющие графы) являются мощным инструментом теоретической информатики и дискретной математики. По-видимому, эффективность экспандеров отчасти объясняется тем, что они (по самому своему определению) позволяют естественно сочетать комбинаторно-геометрические, алгебраические и вероятностные рассуждения.

Экспандеры были определены в 1970-х годах. За прошедшие 40 лет они нашли множество красивых применений. Экспандеры используются в различных конструкциях дерандомизации. С помощью экспандеров строятся помехоустойчивые коды и надёжные вычислительные схемы. Техника экспандеров применяется в различных доказательствах теории сложности вычислений (например, в доказательстве знаменитой PCP-теоремы).

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

Список литературы:

Date and time Class|Name Venue|short Materials
08 April
17:20–18:50
Лекция 1. Комбинаторные экспандеры: определения и теоремы о существовании, Lecture ПОМИ РАН video,  files
08 April
19:10–20:40
Лекция 2. Примеры применений комбинаторных экспандеров, Lecture ПОМИ РАН video,  files
09 April
11:15–12:45
Лекция 3. Вершинное и рёберное расширение графа, Lecture ПОМИ РАН video,  files
09 April
13:00–14:30
Лекция 4. Спектр графа, определение спектрального экспандера, Lecture ПОМИ РАН video,  files
09 April
15:30–17:00
Лекция 5. Спектр случайного графа. Случайное блуждание на экспандере, Lecture ПОМИ РАН video,  files
15 April
17:20–18:50
Лекция 6. Зигзаг-произведение графов, Lecture ПОМИ РАН video,  files
15 April
19:10–20:40
Лекция 7. Рекурсивные конструкции спектральных экспандеров, Lecture ПОМИ РАН video,  files
16 April
11:15–12:45
Лекция 8. Экстракторы случайности, Lecture ПОМИ РАН video,  files
16 April
13:00–14:30
Лекция 9. Генератор Нисана, Lecture ПОМИ РАН video,  files
16 April
15:30–17:00
Лекция 10. Алгоритм Рейнголда. Надежные вычисления, Lecture ПОМИ РАН video,  files