Luca Trevisan mostrou quantas construções de geradores pseudo-aleatórios podem de fato ser consideradas construções de extrator:
http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf
Existe uma conversa significativa? Ou seja, construções "naturais" de extratores podem ser consideradas construções de geradores pseudo-aleatórios (PRG)?
As construções de extratores parecem corresponder a distribuições sobre PRGs (de modo que qualquer distintivo não consiga distinguir quase todas). Existem aplicativos conhecidos para isso?
fonte
Salil Vadhan escreveu para mim que a resposta para minha pergunta é conhecida e os PRGs são equivalentes aos extratores.
Citando-o:
"Veja a Proposição 21 e a discussão a seguir em minha pesquisa http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (há um erro de digitação -" amplificador de dureza de caixa preta "deve ser" preto construção de caixa PRG ")
Diz que extratores são equivalentes a construções PRG de caixa preta, nas quais você se importa apenas com a quantidade de conselhos, e não com o tempo de execução, na redução. Pedir tempo de execução limitado equivale a solicitar extratores com "decodificação de lista local". "
fonte
Há um belo artigo de Chris Umans sobre o análogo desta questão para dispersores: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf
Ele mostra que os dispersores que possuem um procedimento de reconstrução em tempo polinomial, mas não necessariamente a propriedade de decodificação local, implicam na existência de geradores de conjuntos atingidos.
Aqui está outra maneira de visualizá-lo: Os extratores podem ser vistos como códigos recuperáveis por lista (que é uma variante mais forte de códigos decodificáveis por lista) e os PRGs de caixa preta podem ser visualizados por códigos recuperáveis por lista local . Os dispersores podem ser vistos como códigos recuperáveis da lista para erro zero. O que Chris mostra é que um código recuperável de lista para erro zero que possui um procedimento de recuperação de lista em tempo polinomial implica a existência de um código recuperável de lista com o procedimento local de recuperação de lista.
fonte