Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары






Математический кружок
4 марта 2014 г. 17:00–20:00, г. Долгопрудный, 115 КПМ МФТИ
 


Экспандеры и дерандомизация

А. Е. Ромащенко

Институт проблем передачи информации им. А. А. Харкевича РАН, г. Москва

Количество просмотров:
Эта страница:225
Youtube Video:





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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021