Uma comparação de extratores em termos de trocas entre tempo, aleatoriedade e espaço?

21

Existe uma boa pesquisa que compara diferentes extratores, concentradores e superconcentradores e estabeleça os melhores métodos em termos de troca entre aleatoriedade, tempo e espaço?

reference-request randomness derandomization Suresh Venkat
fonte
11
Oi Suresh, eu não acho que extratores e (super) -concentradores são comparáveis. Talvez eu tenha interpretado mal a pergunta, e você quis dizer comparar os algoritmos de construção? Os parâmetros para (super) concentradores com os quais nos preocupamos são suas profundidades e tamanhos, não "aleatoriedade, tempo e espaço". [Artigo de Radhakrishnan e Ta-shma] [1] tem uma tabela mostrando todos os resultados apertados (incluindo referências) para super concentradores. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo
Obrigado pelo esclarecimento. Eu nunca entendi bem as diferenças entre eles.
Suresh Venkat

Respostas:

12

A referência padrão é a pesquisa de Ronen Shaltiel . Isso antecede os resultados importantes de [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] etc. Acredito o doutorado de Anup Rao . Esta tese é uma boa referência recente que descreve esses desenvolvimentos.

arnab
fonte