Redução determinística de erros, estado da arte?

Suponha que um tenha um algoritmo $A$ (BPP) randomizado usando $r$ bits de aleatoriedade. Maneiras naturais de ampliar sua probabilidade de sucesso para $1-\delta$ , para qualquer $\delta>0$ escolhido , são

• Execuções independentes + voto da maioria: execute $A$ independentemente $T=\Theta(\log(1/\delta)$ vezes e faça o voto da maioria das saídas. Isso requer que $rT =\Theta(r\log(1/\delta))$ bits de aleatoriedade e aumenta o tempo de execução por um fator $T=\Theta(\log(1/\delta))$ .
• Execuções independentes em pares + Chebyshev: execute $A$ "em pares de forma independente" $T=\Theta(1/\delta)$ vezes e compare com um limiar Isso requer $rT =\Theta(r/\delta)$ bits de aleatoriedade e aumenta o tempo de execução por um fator $T=\Theta(1/\delta)$ .

Karp, Pippenger e Sipser [1] (aparentemente, eu não poderia chegar em minhas mãos o próprio papel, é uma conta de segunda mão) alternativo fornecido abordagens baseadas em fortes expansores regulares: essencialmente, ver as $2^r$ nós do expansor como as sementes aleatórias. Escolha um nó aleatório do expansor usando os bits aleatórios $r$ e, em seguida,

• faça uma curta caminhada aleatória de comprimento $T=\Theta(\log(1/\delta))$ partir daí e execute $A$ nas sementes $T$ correspondentes aos nós no caminho, antes de obter uma votação majoritária. Isso requer $r+T = r+\Theta(\log(1/\delta))$ bits de aleatoriedade e aumenta o tempo de execução por um fator $T=\Theta(\log(1/\delta))$ .

• execute $A$ em todos os vizinhos do nó atual (ou, de maneira mais geral, em todos os nós a uma distância $c$ do nó atual) antes de fazer uma votação majoritária. Isso requer $r$ bits de aleatoriedade e aumenta o tempo de execução por um fator $T=d$ , onde $d$ é o grau (ou $d^c$ para a distância $c$ vizinha. Configurando bem os parâmetros, isso acaba custando $T=\operatorname{poly}(1/\delta)$ aqui.

Estou interessado no último marcador, que corresponde à redução determinística do erro. Houve alguma melhoria após [1], reduzindo a dependência de $T$ em $\delta$ ? Qual é o melhor desempenho atual - $1/\delta^\gamma$ para o qual $\gamma > 1$ ? $\gamma > 0$ ? (Para $\textsf{BPP}$ ? Para $\textsf{RP}$ ?)

Nota: Também estou (muito) interessado em $\textsf{RP}$ em vez de $\textsf{BPP}$ . Conforme introduzido em [2], a construção relevante não é mais expansora, mas dispersora (veja, por exemplo, essas notas de aula de Ta-Shma, especialmente a Tabela 3). Não consegui encontrar os limites correspondentes para amplificação determinística (nem um bit mais aleatório que o permitido $r$ ), nem (mais importante) quais são as construções explícitas de dispersores de última geração para a faixa relevante de parâmetros. .

[1] Karp, R., Pippenger, N. e Sipser, M., 1985. Uma troca de aleatoriedade no tempo . Na Conferência AMS sobre Complexidade Computacional Probabilística (Vol. 111).

[2] Cohen, A. e Wigderson, A., 1989, outubro. Dispersores, amplificação determinística e fontes aleatórias fracas. No 30º Simpósio Anual de Fundamentos da Ciência da Computação (pp. 14-19). IEEE.

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

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

$\Omega(1/\delta)$