Информация по курсу

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

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

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