Детерминированное снижение ошибок, современное состояние?

12

Предположим, что у каждого есть рандомизированный (BPP) алгоритм A использующий r битов случайности. Естественные способы увеличить вероятность успеха до 1δ для любого выбранного δ>0 :

  • Независимые прогоны + голосование большинством: прогоните A независимо T=Θ(log(1/δ) раз и получите большинство голосов выходов. Для этого требуется rT=Θ(rlog(1/δ)) битов случайности, и увеличивает время работы на коэффициент T=Θ(log(1/δ)) .
  • Попарно независимые прогоны + Чебышев: запустить «попарно независимо друг от друга» Т = Θ ( 1 / б ) раз, и сравнить с порогом Для этого требуется г Т = Θ ( г / δ ) биты случайности и взрывает время работы по Т = Θ ( 1 / δ ) фактор.AT=Θ(1/δ)rT=Θ(r/δ)T=Θ(1/δ)

Karp, Pippenger и Sipser [1] (очевидно, я не мог получить в руки саму бумагу, это подержанный счет), предоставив альтернативные подходы, основанные на сильных регулярных расширителях: по сути, посмотрите 2r узлы расширителя как случайные семена. Выберите случайный узел расширителя, используя r случайных битов, а затем

  • оттуда сделайте короткую случайную прогулку длиной T=Θ(log(1/δ)) и выполните A на T точках T, соответствующих узлам на пути, прежде чем принимать большинство голосов. Это требует r+T=r+Θ(log(1/δ)) битов случайности и увеличивает время работы на коэффициент T=Θ(log(1/δ)) .

  • Выполните A на всех соседях текущего узла (или, в более общем случае, на всех узлах на расстоянии c текущего узла), прежде чем принимать большинство голосов. Это требует r битов случайности и увеличивает время работы на коэффициент T=d , где d - градус (или dc для расстояния c окрестности. При правильной настройке параметров это приводит к стоимости T=poly(1/δ) здесь.

Меня интересует последний пункт, который соответствует снижению детерминированных ошибок. Произошло ли какое-либо улучшение после [1], уменьшающее зависимость T от δ ? Каков наилучший достижимый ток - 1/δγ для которого γ>1 ? γ>0 ? (Для BPP ? Для RP ?)

Примечание: я также (очень) интересуюсь RP вместо BPP . Как было введено в [2], соответствующая конструкция больше не является экспандерами, а диспергаторами (см., Например, эти заметки Та-Шмы, особенно Таблица 3). Однако я не смог найти соответствующих границ для детерминированного (ни на один более случайный бит, чем разрешенный r ) усиления, а также (что более важно), каковы современные явные диспергирующие конструкции для соответствующего диапазона параметров. ,


[1] Карп Р., Пиппенгер Н. и Сипсер М., 1985. Компромисс между случайностью и временем . В конференции AMS по вероятностной вычислительной сложности (том 111).

[2] Коэн А. и Вигдерсон А., 1989, октябрь. Диспергаторы, детерминированное усиление и слабые случайные источники. В 30-м ежегодном симпозиуме по основам информатики (с. 14-19). IEEE.

Климент С.
источник
Мое понимание заключается в следующем ( в основном на вышеупомянутых лекциям Та-Шма , те ван Melkebeek , и те , от Cynthia Дворк . Насколько я могу судить, диспергаторы велики , чтобы усилить экспоненциально данные еще несколько случайных битов , но если есть 0 лишних битов случайности
Клемент С.
poly(1/δ)
1/δ
Также важный (но не дает ответ на конкретный вопрос): Раздел 3.5.4 и Раздел 4 (задача 4.6) из Салили Вадх в псевдослучайности .
Клемент С.

Ответы:

3

O(1/δ)λO(δ)λ=O(1/d)

C/δCO(1/δ)

Ω(1/δ)

гость
источник
α>0dR=2rλδCαCαd(N,d)λC/dNdd=Oα(1/δ)
dd1λ=O(1/d) nnO((log3d)/d)