<p>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: <a href="http://www.cs.bu.edu/~reyzin/hash.html" rel="nofollow">http://www.cs.bu.edu/~reyzin/hash.html</a>.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-17T14:35:36.287Z
2011-01-17T14:35:36.287Z
David Cash
<p>I was reading a paper titled <a href="http://web.cecs.pdx.edu/~teshrim/npro.pdf" rel="nofollow">Random Oracles with(out) Programmability</a>. The last paragraph of section 2.3 reads:</p>

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

<p>I took a look at Wikipedia's entry for <a href="http://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma" rel="nofollow">Borel–Cantelli lemma</a>, 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.</p>

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

CC BY-SA 2.5
2011-01-08T07:09:11.673Z
Tiny commment: The usage of Borel-Cantelli lemma in complexity theory seems to be related to the *resource-bounded measure theory* introduced by [Lutz](http://www.cs.iastate.edu/~lutz/=PAPERS/aehnc.ps), and some follow-ups [here](http://reference.kfupm.edu.sa/content/i/m/improved_resource_bounded_borel_cantelli_1873529.pdf), [here](http://reference.kfupm.edu.sa/content/m/e/measure_on_small_complexity_classes__wit_171201.pdf) and [here](http://www.cse.buffalo.edu/~regan/papers/pdf/RSC95.pdf). I'm also interested in this question, hope that we'll have some nice answers!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-08T09:07:28.903Z
@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" ;)
Sadeq Dousti
CC BY-SA 2.5
2011-01-09T23:54:16.927Z
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
<cc.complexity-theory><derandomization><pr.probability><measure-theory>
Borel-Cantelli Lemma and Derandomization
Sadeq Dousti
# Borel-Cantelli Lemma and Derandomization

(Asked by: username_0 on 2011-01-08)

I was reading a paper titled [Random Oracles with(out) Programmability](http://web.cecs.pdx.edu/~teshrim/npro.pdf). 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](http://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_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.

**Tags:** cc.complexity-theory, derandomization, pr.probability, measure-theory

> **Comments:**
> **username_1**: Tiny commment: The usage of Borel-Cantelli lemma in complexity theory seems to be related to the *resource-bounded measure theory* introduced by [Lutz](http://www.cs.iastate.edu/~lutz/=PAPERS/aehnc.ps), and some follow-ups [here](http://reference.kfupm.edu.sa/content/i/m/improved_resource_bounded_borel_cantelli_1873529.pdf), [here](http://reference.kfupm.edu.sa/content/m/e/measure_on_small_complexity_classes__wit_171201.pdf) and [here](http://www.cse.buffalo.edu/~regan/papers/pdf/RSC95.pdf). I'm also interested in this question, hope that we'll have some nice answers!  
> **username_0**: @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" ;)  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-01-17. Score: 3 | Accepted answer

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.


---

