Home

Семинар 30 марта 2007 года

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

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

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

Abstract

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

Слабый delta-источник случайных битов - это такое распределение на множестве строк длины n, что вероятность каждой конкретной строки не превышает $ 2^{-delta*n} $. В работе показано, как при помощи полиномиального количества случайных битов из такого источника добиться распознавания языка из RP с экспоненциально малой вероятностью ошибки. Доказательство основано на использовании хеш-функций.

Также будет показано важное следствие из этого результата: вероятность ошибки для языка из BPP можно снизить до $ 2^{-2r/3} $, где $ r $ --- длина случайной строки (полиномиально зависящей от размера входа). (Важно, что в вероятности и в длине строки фигурирует одно и то же $ r $.)