Псевдослучайность и дерандомизация (Д.В. Мусатов, осень 2021)
Лектор - Д.В. Мусатов
Время: четверг, 16:30 - 18:30, первое занятие - 9 сентября, ГК 533
Описание
Некоторые задачи решаются рандомизированными алгоритмами. Некоторые алгоритмы, например, проверка простоты числа или проверка связности графа, были дерандомизированы, т.е. превращены в детерминированные из того же сложностного класса (полиномиальное время, логарифмическая память и т.д.). Для других задач, прежде всего проверки арифметического выражения на тривиальность, дерандомизация пока неизвестна. Общий вопрос состоит в том, можно ли избавиться от случайных битов в общем случае или хотя бы существенно сократить их использованное количество. В курсе будет дан обзор классических результатов и новых продвижений по этой теме.