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

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

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

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

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

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

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

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

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

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

$O(1/\delta)$$\lambda$$O(\sqrt{\delta})$$\lambda = O(1/\sqrt{d})$

$C/\delta$$C$$O(1/\delta)$

$\Omega(1/\delta)$