Псевдослучайность и дерандомизация (Д.В. Мусатов, осень 2016)

Лектор — доц. Д.В. Мусатов

Спецкурс проходит по четвергам в 15:00 в ауд. Гарвард в Яндексе. Следующее занятие — 6 октября

Анонс

Существует несколько задач, для которых известен полиномиальный вероятностный алгоритм, но неизвестно полиномиального детерминированного. Тем не менее, многие учёные верят, что все вероятностные алгоритмы в конечном счёте можно дерандомизировать, т.е. P=BPP. В курсе мы познакомимся с причинами этой уверенности и изучим текущие успехи. В частности, мы разберёмся в сложных комбинаторных конструкциях: экспандерах, экстракторах и генераторах псевдослучайных чисел. Курс рассчитан на студентов, знакомых с основами теории сложности вычислений и теории вероятностей.

Программа курса

Программа и ссылки на литературу