Экспандеры и их применения

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

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

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

Подробнее о курсе