Laboratory of Mathematical Logic

Пятница, 30 марта, комната 106. Начало в 15:30.

Докладчик: С. Николенко.

Тема: Моделирование BPP при помощи слабого источника случайных битов.

Abstract

По статье David Zuckerman "Simulating BPP Using a General Weak Random Source".

Слабый delta-источник случайных битов - это такое распределение на множестве строк длины n, что вероятность каждой конкретной строки не превышает

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

Также будет показано важное следствие из этого результата: вероятность ошибки для языка из BPP можно снизить до

, где

--- длина случайной строки (полиномиально зависящей от размера входа). (Важно, что в вероятности и в длине строки фигурирует одно и то же

.)