Lemme Borel-Cantelli et dérandomisation

11

Je lisais un article intitulé Random Oracles with (out) Programmability . Le dernier paragraphe de la section 2.3 se lit comme suit:

[En utilisant notre nouvelle approche], il n'est pas nécessaire d'appliquer des techniques classiques de dérandomisation asymptotique (et uniforme) bien connues basées sur le lemme de Borel-Cantelli . À notre connaissance, cette approche est nouvelle pour cet article.

J'ai jeté un coup d'œil à l'entrée de Wikipédia sur le lemme Borel – Cantelli et j'ai presque saisi l'idée. Cependant, je ne pouvais pas encore comprendre comment cela se rapportait à la dérandomisation. De plus, je ne comprends pas le sens de "asymptotique" et "uniforme" dans le paragraphe susmentionné.

PS: Googler pour Borel-Cantelli et dérandomisation montrera plusieurs résultats intéressants, mais je n'ai pas assez de connaissances pour bien les comprendre.

cc.complexity-theory derandomization pr.probability measure-theory MS Dousti
la source
2
Petit commentaire: L'utilisation du lemme de Borel-Cantelli dans la théorie de la complexité semble être liée à la théorie des mesures limitées par les ressources introduite par Lutz , et à quelques suivis ici , ici et ici . Je suis également intéressé par cette question, j'espère que nous aurons de belles réponses!
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Merci. J'ai aussi vu les œuvres de Lutz, mais elles étaient trop compliquées pour moi :( J'espère que quelqu'un le décrit en "termes profanes";)
MS Dousti
t

Réponses:

3

Je ne pense pas qu'ils signifient dérandomisation au sens traditionnel. Essayez d'examiner l'application du lemme BC dans cet article pour un exemple de ce dont ils parlent: http://www.cs.bu.edu/~reyzin/hash.html .

Ils disent «asymptotique» parce que la plupart des séparations BB s'appliquent à des concepts comme les fonctions unidirectionnelles, qui sont définis asymptotiquement. Leur résultat est plutôt une limite "concrète" qui s'applique à toutes les valeurs des paramètres de sécurité, et pas seulement à des valeurs suffisamment grandes.

David Cash
la source