Deterministyczna redukcja błędów, najnowocześniejszy?

Załóżmy, że jeden ma losowy (BPP) algorytm $A$ przy użyciu $r$ bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do $1-\delta$ dla każdego wybranego $\delta>0$

• Niezależne przebiegi + większość głosów: przebieg $A$ niezależnie $T=\Theta(\log(1/\delta)$ razy ) i przyjmowanie większości głosów z wyjść. Wymaga to $rT =\Theta(r\log(1/\delta))$ bitów losowości i wydłuża czas działania o współczynnik $T=\Theta(\log(1/\delta))$ .
• Przebiegi niezależne od par + Czeczeszew: uruchom $A$ „parami niezależnie” $T=\Theta(1/\delta)$ razy i porównaj z progiem Wymaga to losowości $rT =\Theta(r/\delta)$ i wydłuża czas działania o współczynnik $T=\Theta(1/\delta)$ .

Karp, Pippenger i Sipser [1] (podobno, nie mogłem dostać w swoje ręce samego papieru, jest to konto z drugiej ręki), pod warunkiem, alternatywne podejścia oparte na silnych regularnych ekspanderów: w zasadzie, patrz $2^r$ węzły ekspandera jak losowe nasiona. Wybierz losowy węzeł ekspandera za pomocą $r$ losowych bitów, a następnie

• stamtąd wykonaj krótki losowy spacer o długości $T=\Theta(\log(1/\delta))$ i uruchom $A$ na nasionach $T$ odpowiadających węzłom na ścieżce, zanim przejmiesz większość głosów. Wymaga to $r+T = r+\Theta(\log(1/\delta))$ bitów losowości i wysadza czas działania o współczynnik $T=\Theta(\log(1/\delta))$ .

• uruchom $A$ na wszystkich sąsiadach bieżącego węzła (lub, bardziej ogólnie, na wszystkich węzłach w odległości $c$ od bieżącego węzła) przed przejęciem większości głosów. Wymaga to $r$ bitów losowości i wydłuża czas działania o współczynnik $T=d$ , gdzie $d$ jest stopniem (lub $d^c$ dla sąsiedztwa odległości $c$ . Dobrze skonfigurowanie parametrów, co ostatecznie kosztuje $T=\operatorname{poly}(1/\delta)$ tutaj.

Interesuje mnie ostatni punkt, który odpowiada deterministycznej redukcji błędów. Czy nastąpiła poprawa po [1], zmniejszająca zależność $T$ od $\delta$ ? Co jest obecnie najlepiej osiągalnym - $1/\delta^\gamma$ dla którego $\gamma > 1$ ? $\gamma > 0$ ? (Dla $\textsf{BPP}$ ? Dla $\textsf{RP}$ ?)

Uwaga: Interesuje mnie również (bardzo) $\textsf{RP}$ zamiast $\textsf{BPP}$ . Jak wprowadzono w [2], odpowiednią konstrukcją nie są już ekspandery, lecz rozpraszacze (patrz np. Notatki do wykładu Ta-Shmy, zwłaszcza Tabela 3). Nie mogłem jednak znaleźć odpowiednich granic dla deterministycznego (ani jednego bardziej losowego bitu niż dozwolone $r$ ) wzmocnienia, ani (co ważniejsze) jakie są najnowocześniejsze konstrukcje jawnego rozpraszacza dla odpowiedniego zakresu parametrów .

[1] Karp, R., Pippenger, N. i Sipser, M., 1985. Kompromis czasowo-losowy . Na konferencji AMS nt. Probabilistycznej złożoności obliczeniowej (tom 111).

[2] Cohen, A. i Wigderson, A., 1989, październik. Dyspergatory, deterministyczne wzmocnienie i słabe źródła losowe. W 30. dorocznym sympozjum na temat podstaw informatyki (s. 14–19). IEEE.

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

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

$\Omega(1/\delta)$