Laboratory of Mathematical Logic at PDMI

Пятница, 15 декабря, комната 106. Начало в 16:00.

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

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

Abstract

Вторая лекция миникурса будет посвящена посвящена следующим графам: мажорирующим дисперсерам и экстракторам. Будет показана связь этих понятий с понижением вероятности ошибки в случае вычислений с двусторонней ошибкой. Будут представлены конструкции экстракторов.

Слайды первой лекции доступны по адресу http://logic.pdmi.ras.ru/~dmitrits/talks/derand1.pdf .