Lema de Borel-Cantelli y desrandomización

11

Estaba leyendo un artículo titulado Random Oracles with (out) Programmability . El último párrafo de la sección 2.3 dice:

[Utilizando nuestro enfoque novedoso] no hay necesidad de aplicar técnicas de desrandomización asintóticas clásicas (y uniformes) bien conocidas basadas en el lema de Borel-Cantelli . Hasta donde sabemos, este enfoque es novedoso en este documento.

Eché un vistazo a la entrada de Wikipedia para el lema de Borel-Cantelli , y casi entendí la idea. Sin embargo, aún no podía entender cómo se relaciona con la desrandomización. Además, no entiendo el significado de "asintótico" y "uniforme" en el párrafo mencionado.

PD: Buscar en Google Borel-Cantelli y la desrandomización mostrarán varios resultados interesantes, pero no tengo suficientes antecedentes para entenderlos bien.

cc.complexity-theory derandomization pr.probability measure-theory MS Dousti
fuente
2
Comentario minúsculo: el uso del lema de Borel-Cantelli en la teoría de la complejidad parece estar relacionado con la teoría de la medida limitada por los recursos introducida por Lutz , y algunos seguimientos aquí , aquí y aquí . También estoy interesado en esta pregunta, ¡espero que tengamos algunas buenas respuestas!
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Gracias. También vi las obras de Lutz, pero eran demasiado complicadas para mí :( Espero que alguien lo describa en "términos simples";)
MS Dousti
t

Respuestas:

3

No creo que signifiquen aleatorización en el sentido tradicional. Intente ver la aplicación del lema de BC en este documento para ver un ejemplo de lo que están hablando: http://www.cs.bu.edu/~reyzin/hash.html .

Dicen "asintótico" porque la mayoría de las separaciones BB se aplican a conceptos como funciones unidireccionales, que se definen asintóticamente. Su resultado es, en cambio, un límite "concreto" que se aplica a todos los valores de los parámetros de seguridad, no solo a valores suficientemente grandes.

David Cash
fuente