Выполнение алгоритма BPP с полу-случайной, полу-состязательной строкой

Рассмотрим следующую модель: n-битная строка r = r ₁ ... r _n выбирается случайным образом равномерно. Далее каждый индекс i∈ {1, ..., n} помещается в множество A с независимой вероятностью 1/2. Наконец, противнику разрешено, для каждого i∈A отдельно, перевернуть r _i, если он этого хочет.

Мой вопрос заключается в следующем: может ли полученная строка (назовем ее r ') использоваться алгоритмом RP или BPP в качестве единственного источника случайности? Предположим, что злоумышленник заранее знает весь алгоритм BPP, строку r и множество A и что у него неограниченное время вычислений. Также предположим (очевидно), что алгоритм BPP не знает ни флип-решений противника, ни A.

Я хорошо знаю, что есть длинный ряд работ по именно этому вопросу, от работы Умеша Вазирани над полуслучайными источниками (другая, но связанная модель), до более поздней работы по экстракторам, слияниям и конденсаторам. Поэтому мой вопрос заключается в том, что любая из этих работ дает то, что я хочу! Литература о слабых случайных источниках настолько велика, с таким количеством тонко различающихся моделей, что тот, кто знает эту литературу, может сэкономить мне много времени. Заранее спасибо!

То, что вам нужно, - это «выделенный экстрактор» со следующими параметрами: начальное число длины , грубая случайность и выходная длина . Это известно. Хотя я не в курсе последних опросов, я полагаю, что третьего раздела опроса Ронена достаточно.$O(\log n)$$n/2$$n^{\Omega(1)}$

Единственное, что вам нужно показать, это то, что ваш источник имеет достаточную «минимальную энтропию», то есть ни одна n-битная строка не получает вероятность более , что, я думаю, ясно в ваших настройках.$2^{-n/2}$

Разрешено ли противнику видеть всю строку r, прежде чем решить, как установить биты в A? Если ответ «нет», то это источник исправления битов, который на самом деле детерминированно извлекается. То есть, действительно случайное семя не требуется. См., Например, Kamp и Zuckerman для конструкций экстракторов для источников фиксации битов.

Если злоумышленнику разрешено видеть остальную часть строки, я все равно догадываюсь, что она детерминированно извлекается, но модели немного отличаются, и я не знаю, как они связаны. Поскольку набор A является случайным, на самом деле он даже более дружественный, чем источник с фиксацией битов, где набор A может быть произвольным.

Ноам прав, конечно. Исторически первое моделирование BPP с источником любой постоянной скорости энтропии было дано в моей статье «Моделирование BPP с использованием общего слабого случайного источника». Теперь есть более простые способы достижения этого и еще более сильные результаты.

Детерминированное извлечение более чем постоянного числа битов невозможно в вашей модели. (Вы можете получить слабое детерминированное извлечение 1 бита, просто выводя первый бит.) Кэмп и я показали, что невозможно извлечь больше, чем постоянное количество бит в общем не забывающем источнике фиксации битов с постоянной скоростью энтропии, но так как множество A является случайным, эти результаты не применяются, как указано. Однако наше доказательство сработало, выбрав A случайным образом с фиксированным размером t, поэтому, выбрав t = .6n, скажем, будет получен результат для равномерно случайного A.