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

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

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

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

• 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. Cambridge University Press.

• N. Alon, J.H. Spencer. The Probabilistic Method. Wiley-Interscience Publication. Русский перевод: Н. Алон, Дж. Спенсер. Вероятностный метод. Бином. Лаборатория знаний, 2007