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

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

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

Основная литература:

• S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, vol. 43, Number 4, Oct. 2006, pp.439-561.
• S. Arora, B. Barak. Computational Complexity: A modern Approach. Draft. http://www.cs.princeton.edu/theory/complexity/
• N. Alon, J. H. Spencer. The Probabilistic Method. 2nd ed. Wiley-Interscience Publication.

Список упражнений

Конспект

Лекции:

1. Опеределение расширяющего графа (экспандера). Вероятностное доказательство существования экспандеров. Примеры применений экспандеров: конструкция кодов, исправляющих ошибки; уменьшения ошибки в вероятностных алгоритмах (без увеличения числа случайных битов); компактное хранение множества с быстрой процедурой запроса элементов.
2. Матрица графа, комбинаторный смысл её собственных чисел. Алгебраическое определение экспандера. Лемма о перемешивании. Свойство рёберного расширения. Нижняя граница для второго собственного числа.
3. Существование алгебраических экспандеров: большинство d-регулярных экспандеров являются экспандерами (доказательство методом моментов).
4. Произведения графов: матричное произведение, тензорное произведение, простой и сбалансированный варианты подстановочного произведения, зигзаг-произведение. 5. Оценка второго собственного числа в графе зигзаг-произведения. Явное построение экспандеров (рекурсивная конструкция с зигзаг-произведением).
5. Оценка второго собственного числа для сбалансированного подстановочного произведения. Вторая явная конструкция экспандера (рекурсивная конструкция с подстановочным произведением).
6. Вычисление спектра для графа аффинной плоскости. Использование графа аффинной плоскости в явных конструкцих экспандеров.
7. Графы Кэли. Спектр графа Кэли для конечных абелевых групп. Графы Рамануджана.
8. Алгоритм Рейнголда: решение задачи UPATH детерминированным алгоритмом с логарифмической памятью.
9. Ещё раз об экспандерных кодах: коды Земора.
10. Построение схем из функциональных элементов, устойчивых к ошибкам. Явная конструкция графа--компрессора.