# Borel-Cantelli Lemma and Derandomization

I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads:

[Using our novel approach] there is no need to apply well-known classical asymptotic (and uniform) derandomization techniques based on the Borel-Cantelli lemma. To the best of our knowledge, this approach is novel to this paper.

I took a look at Wikipedia's entry for Borel–Cantelli lemma, and almost grasped the idea. However, I couldn't still figure out how it relates to derandomization. In addition, I don't understand the meaning of "asymptotic" and "uniform" in the aforementioned paragraph.

PS: Googling for Borel-Cantelli and derandomization will show several interesting results, but I don't have enough background to understand them well.

• Tiny commment: The usage of Borel-Cantelli lemma in complexity theory seems to be related to the resource-bounded measure theory introduced by Lutz, and some follow-ups here, here and here. I'm also interested in this question, hope that we'll have some nice answers! – Hsien-Chih Chang 張顯之 Jan 8 '11 at 7:09
• @Hsien-Chih: Thanks. I also saw Lutz's works, but they were too complicated for me :( I hope someone describes it in "layman's terms" ;) – M.S. Dousti Jan 8 '11 at 9:07
• I guess that if your random events are something like line of code executed at time step $t$ and you can apply Borel-Cantelli, then your program terminates always. – Raphael Jan 9 '11 at 23:54