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.

  • 2
    $\begingroup$ 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! $\endgroup$ Jan 8 '11 at 7:09
  • $\begingroup$ @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" ;) $\endgroup$ Jan 8 '11 at 9:07
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Jan 9 '11 at 23:54

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.