Лекции А. Е. Ромащенко по экспандерам

45 подписчиков

С 28-го марта по 5-е апреля в рамках Computer Science клуба при ПОМИ РАН Андрей Евгеньевич Ромащенко ( Институт проблем передачи информации РАН) прочтёт курс лекций по экспандерам. Экспандеры (расширяющие графы) являются мощным и весьма изощрённым инструментом теоретической информатики и дискретной математики. По–видимому, эффективность экспандеров отчасти объясняется тем, что они (по самому своему определению) позволяют естественно сочетать комбинаторно–геометрические, алгебраические и вероятностные рассуждения. Экспандеры были определены в 1970–х годах. За прошедшие 30 лет они нашли множество красивых применений. Экспандеры используются в различных конструкциях дерандомизации. С помощью экспандеров строятся коды, исправляющие ошибки, и надёжные вычислительные схемы. Техника экспандеров применяется в различных доказательствах теории сложности вычислений (например, в доказательстве знаменитой PCP–теоремы)… В данном курсе мы будем интересоваться экспандерами с точки зрения теории алгоритмов. Мы изучим связь комбинаторных и спектральных свойств экспандеров, рассмотрим эффективные алгоритмические методы построения таких графов, а также обсудим различные применения экспандеров. Мы также поговорим о связи экспандеров с другими замечательными классами графов: экстракторами, дисперсерами, компрессорами.