Аннотация:
Экспандерами (расширяющими графами) называют разреженные графы, обладающими особыми свойствами перемешивания, вершинного и рёберного расширения. Понятие экспандера возникло в 1970-х годах в работах Л.А.Бассалыго, М.С.Пинскера, и Г.А.Маргулиса. Почти все однородные разреженные графы являются экспандерами; однако очень непросто построить такой граф явно. На Западе интерес к экспандерам активизировался в 1990-е годы. Эти графы оказались эффективным инструментом во многих приложениях, прежде всего в теории сложности вычислений и в теории кодирования. С другой стороны, построение экспандеров оказалось связано с глубокими вопросами алгебры и комбинаторики.
В данной лекции мы поговорим об основных свойствах экспандеров, а также обсудим несколько примеров применения экспандеров в информатике.
Обратная связь: