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.

— Klemens C.
źródło

Rozumiem, co następuje (głównie w wyżej wspomnianych notatkach z wykładów Ta-Shmy , te van van Melkebeka i te autorstwa Cynthii Dwork . O ile wiem, dyspergatory są świetne do wykładniczego wzmocnienia, biorąc pod uwagę kilka losowych bitów , ale nie jeśli jest 0 dodatkowych bitów losowości

— Clement C.

p o l y (1 / δ)

$\mathrm{poly}(1/\delta)$

1 / δ

$1/\delta$

Istotne (ale nie odpowiada na konkretne pytanie): sekcja 3.5.4 i sekcja 4 (problem 4.6) pseudolosowości Salila Vadhana .

— Clement C.

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

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

$\Omega(1/\delta)$

— Gość
źródło

α > 0

$\alpha>0$

d

$d$

R = 2^{r}

$R=2^r$

λ \leq \sqrt{δ} \cdot C_{α}

$\lambda \leq \sqrt{\delta}\cdot C_\alpha$

C_{α}

$C_\alpha$

d

$d$

(N, d)

$(N,d)$

λ \leq C / \sqrt{d}

$\lambda \leq C/\sqrt{d}$

N

$N$

d

$d$

d = O_{α} (1 / δ)

$d = O_\alpha(1/\delta)$

d

$d$

d - 1

$d-1$

λ = O (1 / \sqrt{d})

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

n

$n$

n

$n$

O (\sqrt{(\log^{3} d) / d})

$O(\sqrt{(\log^3 d)/d})$