Executando um algoritmo BPP com uma sequência meio aleatória e meio contraditória

Considere o seguinte modelo: uma sequência de n bits r = r ₁ ... r _n é escolhida uniformemente aleatoriamente. Em seguida, cada índice i∈ {1, ..., n} é colocado em um conjunto A com probabilidade independente 1/2. Finalmente, um adversário é permitido, para cada i∈A separadamente, para r aleta _i se quiser.

Minha pergunta é a seguinte: a sequência resultante (chamada r ') pode ser usada por um algoritmo RP ou BPP como sua única fonte de aleatoriedade? Suponha que o adversário conheça com antecedência todo o algoritmo BPP, a string r e o conjunto A, e que tenha tempo de computação ilimitado. Suponha também (obviamente) que o algoritmo BPP não conhece as decisões invertidas do adversário nem o A.

Estou ciente de que há uma longa linha de trabalho sobre exatamente esse tipo de pergunta, do trabalho de Umesh Vazirani sobre fontes semi-aleatórias (um modelo diferente, mas relacionado), ao trabalho mais recente sobre extratores, fusões e condensadores. Portanto, minha pergunta é simplesmente se algum desses trabalhos produz o que eu quero! A literatura sobre fontes aleatórias fracas é tão grande, com tantos modelos sutilmente diferentes, que alguém que conhece essa literatura provavelmente pode me economizar muito tempo. Desde já, obrigado!

O que você precisa é de um "extrator semeado" com os seguintes parâmetros: semente do comprimento , aleatoriedade bruta n / 2 e comprimento da saída n Ω ( 1 ) . Estes são conhecidos. Embora eu não esteja atualizado com as pesquisas mais recentes, acredito que a seção 3 da pesquisa de Ronen é suficiente.$O(\log n)$$n/2$$n^{\Omega(1)}$

$2^{-n/2}$

É permitido ao adversário ver a sequência inteira r antes de decidir como definir os bits em A? Se a resposta for negativa, essa é uma fonte de correção de bits, que é realmente deterministicamente extraível. Ou seja, nenhuma semente verdadeiramente aleatória é necessária. Veja, por exemplo, Kamp e Zuckerman para construções de extratores para fontes de correção de bits.

Se o adversário tiver permissão para ver o resto da sequência, eu ainda acho que é deterministicamente extraível, mas os modelos são um pouco diferentes e não sei de que maneira eles se relacionam. Como o conjunto A é aleatório, na verdade é ainda mais amigável que uma fonte de correção de bits, onde o conjunto A pode ser arbitrário.

Noam está certo, é claro. Historicamente, a primeira simulação de BPP com uma fonte de qualquer taxa de entropia constante foi apresentada em meu artigo "Simulando BPP usando uma fonte aleatória fraca geral". Agora, existem maneiras mais simples de conseguir isso e resultados ainda mais fortes.

A extração determinística de mais do que um número constante de bits é impossível no seu modelo. (Você pode obter uma extração determinística fraca de 1 bit simplesmente emitindo o primeiro bit.) Kamp e eu mostramos que é impossível extrair mais do que um número constante de bits em uma fonte geral de correção de bits não esquecida, com taxa de entropia constante, mas como o conjunto A é aleatório, esses resultados não se aplicam como indicado. No entanto, nossa prova funcionou escolhendo A aleatoriamente com um tamanho fixo t; portanto, escolhendo t = 0,6n, digamos, o resultado para um A uniformemente aleatório se seguirá.