Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 1. Комбинаторные экспандеры: определения и простейшие применения
Экспандеры и их применения


Что: Лекция
Когда: Вторник, 04 апреля 2017, 11:50–13:20
Где: 2-й учебный корпус К(П)ФУ, ауд. 1011

Описание

Определения однородного комбинаторного экспандера. Вероятностное доказательство существования.

Коэффиценты вершинного и рёберного расширения. Соотношние трёх определений: коэффиценты вершинного и рёберного расширения и определения однородного комбинаторного экспандера.

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

Приложенные файлы