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.
I don't think they mean derandomization in the traditional sense.  Try looking at the application of the BC lemma in this paper for an example of what they are talking about: http://www.cs.bu.edu/~reyzin/hash.html.

They say "asymptotic" because most BB separations apply to concepts like one-way functions, which are defined asymptotically.  Their result is instead a "concrete" bound that applies to all values of the security parameters, not just sufficiently large values.