Eu estava lendo um artigo intitulado Random Oracles com (fora) programação . O último parágrafo da seção 2.3 diz:
[Usando nossa nova abordagem], não há necessidade de aplicar técnicas clássicas conhecidas de derandomização assintótica (e uniforme) com base no lema de Borel-Cantelli . Até onde sabemos, essa abordagem é uma novidade para este artigo.
Dei uma olhada na entrada da Wikipedia para o lema de Borel – Cantelli e quase compreendi a idéia. No entanto, eu ainda não conseguia descobrir como isso se relaciona com a des randomização. Além disso, não entendo o significado de "assintótico" e "uniforme" no parágrafo acima mencionado.
PS: Pesquisando no Borel-Cantelli e derandomization , mostraremos vários resultados interessantes, mas não tenho experiência suficiente para entendê-los bem.
Respostas:
Eu não acho que eles significam des aleatorização no sentido tradicional. Tente examinar a aplicação do lema da BC neste artigo para obter um exemplo do que eles estão falando: http://www.cs.bu.edu/~reyzin/hash.html .
Eles dizem "assintóticos" porque a maioria das separações de BB se aplica a conceitos como funções unidirecionais, que são definidas assintoticamente. O resultado é um limite "concreto" que se aplica a todos os valores dos parâmetros de segurança, não apenas aos valores suficientemente grandes.
fonte