Exécution d'un algorithme BPP avec une chaîne mi-aléatoire, mi-contradictoire

Considérons le modèle suivant: une chaîne de n bits r = r ₁ ... r _n est choisie uniformément au hasard. Ensuite, chaque indice i∈ {1, ..., n} est placé dans un ensemble A avec une probabilité indépendante 1/2. Enfin, un adversaire est autorisé, pour chaque i∈A séparément, à retourner r _i s'il le souhaite.

Ma question est la suivante: la chaîne résultante (appelez-la r ') peut-elle être utilisée par un algorithme RP ou BPP comme seule source d'aléatoire? Supposons que l'adversaire connaisse à l'avance tout l'algorithme BPP, la chaîne r et l'ensemble A, et qu'il dispose d'un temps de calcul illimité. Supposons également (évidemment) que l'algorithme BPP ne connaît ni les décisions de retournement de l'adversaire ni A.

Je suis bien conscient qu'il existe une longue ligne de travail sur ce type de question, des travaux d'Umesh Vazirani sur les sources semi-aléatoires (un modèle différent mais lié) aux travaux plus récents sur les extracteurs, les fusions et les condenseurs. Ma question est donc simplement de savoir si l'un de ces travaux donne ce que je veux! La littérature sur les sources aléatoires faibles est si vaste, avec tellement de modèles subtilement différents, que quelqu'un qui sait que la littérature peut probablement me faire gagner beaucoup de temps. Merci d'avance!

Ce dont vous avez besoin est un "extracteur ensemencé" avec les paramètres suivants: graine de longueur , aléatoire aléatoire n / 2 et longueur de sortie n Ω ( 1 ) . Celles-ci sont connues. Bien que je ne sois pas au courant des sondages les plus récents, je pense que la section 3 du sondage de Ronen est suffisante.$O(\log n)$$n/2$$n^{\Omega(1)}$

La seule chose que vous devrez montrer est que votre source a une "entropie min" suffisante, c'est-à-dire qu'aucune chaîne de n bits n'obtient une probabilité supérieure à $2^{-n/2}$

L'adversaire est-il autorisé à voir la chaîne entière r avant de décider comment définir les bits dans A? Si la réponse est non, il s'agit d'une source de correction de bits, qui est en fait extractible de façon déterministe. Autrement dit, aucune graine vraiment aléatoire n'est requise. Voir, par exemple, Kamp et Zuckerman pour les constructions d'extracteurs pour les sources de fixation de bits.

Si l'adversaire est autorisé à voir le reste de la chaîne, je suppose qu'il est extractible de manière déterministe, mais les modèles sont légèrement différents et je ne sais pas du haut de ma tête comment ils se rapportent. Étant donné que l'ensemble A est aléatoire, il est en fait encore plus convivial qu'une source de correction de bits, où l'ensemble A peut être arbitraire.

Noam a raison, bien sûr. Historiquement, la première simulation de BPP avec une source de tout taux d'entropie constant a été donnée dans mon article "Simuler le BPP en utilisant une source aléatoire faible générale". Il existe désormais des moyens plus simples d'y parvenir et des résultats encore plus solides.

Une extraction déterministe de plus d'un nombre constant de bits est impossible dans votre modèle. (Vous pouvez obtenir une extraction déterministe faible de 1 bit en émettant simplement le premier bit.) Kamp et moi avons montré qu'il est impossible d'extraire plus d'un nombre constant de bits dans une source de fixation de bits générale non inconsciente avec un taux d'entropie constant, mais comme l'ensemble A est aléatoire, ces résultats ne s'appliquent pas comme indiqué. Cependant, notre preuve a fonctionné en choisissant A au hasard d'une taille fixe t, donc en choisissant t = 0,6n, disons, le résultat pour un A uniformément aléatoire suivra.