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

12

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

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

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 2r 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=Θ(log(1/δ)) 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+Θ(log(1/δ)) bits de aleatoriedade e aumenta o tempo de execução por um fator T=Θ(log(1/δ)) .

  • 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 dc para a distância c vizinha. Configurando bem os parâmetros, isso acaba custando T=poly(1/δ) 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 δ ? Qual é o melhor desempenho atual - 1/δγ para o qual γ>1 ? γ>0 ? (Para BPP ? Para RP ?)

Nota: Também estou (muito) interessado em RP em vez de 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.

Clemente C.
fonte
Meu entendimento é o seguinte (principalmente nas notas de Ta-Shma mencionadas anteriormente , as de van Melkebeek e as de Cynthia Dwork . Até onde eu sei, dispersores são ótimos para amplificar exponencialmente dados mais alguns bits aleatórios , mas não se existem 0 bits extras de aleatoriedade.
Clement C.
(se alguém estiver disposto a usar esses poucos bits extras, a palestra de Ta-Shma terá um conjunto muito completo de tabelas resumidas). Sem aleatoriedade extra, a abordagem BPP / RP baseada em expansor parece a única (consulte as notas de van Melkebeek para BPP, as de Dwork para a variante RP: ambas são muito semelhantes e baseadas no artigo [1], do qual eu não foi possível encontrar um pdf direto). Nenhum parece dar uma explícita ligado no grau do polinómio no , uma vez que depende do grau de expansão e do gráfico expansor. poly(1/δ)
Clement C.
Será pelo menos linear em : mas o que será para as construções (atuais) mais conhecidas dos gráficos de expansão? Na verdade, mesmo para construções probabilísticas? 1/δ
Clement C.
Também relevante (mas não responde à pergunta específica): Seção 3.5.4 e Seção 4 (Problema 4.6) de do Salil Vadhan pseudo-aleatoriedade .
Clement C.

Respostas:

3

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

C/δCO(1/δ)

Ω(1/δ)

hóspede
fonte
α>0dR=2rλδCαCαd(N,d)λC/dNdd=Oα(1/δ)
dd1λ=O(1/d) nnO((log3d)/d)