Laboratory of Mathematical Logic at PDMI

Пятница, 1 декабря, комната 106. Начало в 14:20.

Докладчик: Д. Ицыксон.

Тема: Дерандомизация алгоритмов. Основные подходы и результаты. Экспандеры, дисперсеры, экстракторы.

Abstract

Первая лекция МИНИКУРСА будет посвящена посвящена понижению вероятности ошибки без использования дополнительных случайных битов (и с использованием небольшого числа их). Будет дано определение графов-дисперсеров, показана их связь с дерандомизацией, а также будет приведено несколько конструкций дисперсеров.