Пятница, 30 марта, комната 106. Начало в 15:30.
Докладчик: С. Николенко.
Тема: Моделирование BPP при помощи слабого источника случайных битов.
По статье David Zuckerman "Simulating BPP Using a General Weak Random Source".
Слабый delta-источник случайных битов - это такое распределение на множестве строк длины n, что вероятность каждой конкретной строки не превышает . В работе показано, как при помощи полиномиального количества случайных битов из такого источника добиться распознавания языка из RP с экспоненциально малой вероятностью ошибки. Доказательство основано на использовании хеш-функций.
Также будет показано важное следствие из этого результата: вероятность ошибки для языка из BPP можно снизить до , где
--- длина случайной строки (полиномиально зависящей от размера входа). (Важно, что в вероятности и в длине строки фигурирует одно и то же
.)