<p>How about Welzl's randomized algorithm for minimal enclosing ellipsoids? It has recursion depth O(d) where d is the dimension of the space.</p>

<p>I know next to nothing about derandomization, so this might not be what you're looking for. If my example doesn't qualify (maybe by your definition it only makes inessential use of recursion?), perhaps you could clarify why that is. That would increase the chances of higher quality, more pertinent answers from others.</p>

CC BY-SA 2.5
2010-09-24T09:33:35.643Z
I am not aware of this algorithm. Thanks for pointing it. Lets say the stack is inessential if removing the stack incurs only a slight increase in running time. I don't have example of recursive randomized algorithms that don't make essential use of the stack.
Shiva Kintali
CC BY-SA 2.5
2010-09-24T04:23:52.197Z
2010-09-24T04:23:52.197Z
Per Vognsen
<p>The faster version of the min-cut algorithm is very recursive indeed. See figure 2.5 <a href="http://valis.cs.uiuc.edu/~sariel/teach/10/a_rand_alg/lec/02_mincut.pdf" rel="nofollow">here</a>, or any standard randomized algorithms textbook.</p>

CC BY-SA 2.5
2010-09-25T05:58:55.383Z
Thats an excellent example as well
Suresh Venkat
CC BY-SA 2.5
2010-09-25T04:39:36.997Z
2010-09-25T04:39:36.997Z
Sariel Har-Peled
<p>As Per Vognsen points out, and more generally as well, there are many geometric algorithms that operate as follows: Pick a random sample, and run recursively on the sample and on other structures derived thereof. Clarkson's randomized algorithm for linear programming, as well as Seidel's, and indeed the Matousek-Sharir-Welzl series that Per mentions, all operate in this manner, and Clarkson's paradigm extends to other situations where you build some kind cutting or epsilon-net and recurse. </p>

<p>Unfortunately, you're unlikely to get a <em>new</em> result from this, because there are optimal derandomizations of these algorithms, due to work by Matousek, and Chazelle. <a href="http://www.cs.princeton.edu/~chazelle/pubs/CuttingHyperplanes.pdf">Chazelle's paper</a> is a good reference point for this work and prior work by Matousek. But it might be a good test of your method: it was hard to come up with these derandomizations, and if your method provides a black box approach starting with the (easier) randomized algorithm, that would be neat. </p>

<p>p.s this is probably the most boring example possible, but does your method work on quicksort, or any of the randomized median finding methods ? </p>

CC BY-SA 2.5
2010-09-24T09:42:58.837Z
Yes. My approach is a black-box method. It doesn't seem to work on quicksort or randomized median finding methods. I will go through Chazelle's paper. Thanks.
Shiva Kintali
CC BY-SA 2.5
2010-09-24T04:27:51.480Z
2010-09-24T04:27:51.480Z
Suresh Venkat
<p>I have developed a new derandomization technique which is aimed at recursive randomized algorithms (or) more generally randomized algorithms that use a stack. Unfortunately, I could not find natural randomized algorithms to apply my techniques. <a href="http://portal.acm.org/citation.cfm?id=1462154">Recursive Markov Chains and Stochastic grammars</a> are very close to what I am looking for. Are there other (more natural) randomized algorithms that make "essential" use of stack ? Any help is greatly appreciated, since I am stuck with this for more than six months now.</p>

<p>To give you more context, I am looking for a list of problems similar to those in <a href="http://portal.acm.org/citation.cfm?id=509996">SivaKumar's Paper</a>. Note that SivaKumar used Nisan's Pseudo-random generator to derandomize these problems.</p>

CC BY-SA 2.5
2010-09-24T04:16:27.643Z
Could you give examples of recursive randomized algorithms that don't make essential use of the stack? How about Welzl's randomized algorithm for minimal enclosing ellipsoids with recursion depth O(d) where d is the dimension of the space.
Per Vognsen
CC BY-SA 2.5
2010-09-24T04:20:17.203Z
You should make this an answer !
Suresh Venkat
<randomness><derandomization>
Randomized algorithms using a stack
Shiva Kintali
# Randomized algorithms using a stack

(Asked by: username_0 on 2010-09-23)

I have developed a new derandomization technique which is aimed at recursive randomized algorithms (or) more generally randomized algorithms that use a stack. Unfortunately, I could not find natural randomized algorithms to apply my techniques. [Recursive Markov Chains and Stochastic grammars](http://portal.acm.org/citation.cfm?id=1462154) are very close to what I am looking for. Are there other (more natural) randomized algorithms that make "essential" use of stack ? Any help is greatly appreciated, since I am stuck with this for more than six months now.

To give you more context, I am looking for a list of problems similar to those in [SivaKumar's Paper](http://portal.acm.org/citation.cfm?id=509996). Note that SivaKumar used Nisan's Pseudo-random generator to derandomize these problems.

**Tags:** randomness, derandomization
> **Comments:**
> **username_1**: Could you give examples of recursive randomized algorithms that don't make essential use of the stack? How about Welzl's randomized algorithm for minimal enclosing ellipsoids with recursion depth O(d) where d is the dimension of the space.  
> **username_2**: You should make this an answer !  

---

## 3 answers

### Answer by username_2 on 2010-09-24. Score: 6 | Accepted answer

As Per Vognsen points out, and more generally as well, there are many geometric algorithms that operate as follows: Pick a random sample, and run recursively on the sample and on other structures derived thereof. Clarkson's randomized algorithm for linear programming, as well as Seidel's, and indeed the Matousek-Sharir-Welzl series that Per mentions, all operate in this manner, and Clarkson's paradigm extends to other situations where you build some kind cutting or epsilon-net and recurse.

Unfortunately, you're unlikely to get a *new* result from this, because there are optimal derandomizations of these algorithms, due to work by Matousek, and Chazelle. [Chazelle's paper](http://www.cs.princeton.edu/~chazelle/pubs/CuttingHyperplanes.pdf) is a good reference point for this work and prior work by Matousek. But it might be a good test of your method: it was hard to come up with these derandomizations, and if your method provides a black box approach starting with the (easier) randomized algorithm, that would be neat.

p.s this is probably the most boring example possible, but does your method work on quicksort, or any of the randomized median finding methods ?

> **Comments:**
> **username_0**: Yes. My approach is a black-box method. It doesn't seem to work on quicksort or randomized median finding methods. I will go through Chazelle's paper. Thanks.  

---

### Answer by username_1 on 2010-09-24. Score: 6

How about Welzl's randomized algorithm for minimal enclosing ellipsoids? It has recursion depth O(d) where d is the dimension of the space.

I know next to nothing about derandomization, so this might not be what you're looking for. If my example doesn't qualify (maybe by your definition it only makes inessential use of recursion?), perhaps you could clarify why that is. That would increase the chances of higher quality, more pertinent answers from others.

> **Comments:**
> **username_0**: I am not aware of this algorithm. Thanks for pointing it. Lets say the stack is inessential if removing the stack incurs only a slight increase in running time. I don't have example of recursive randomized algorithms that don't make essential use of the stack.  

---

### Answer by username_3 on 2010-09-25. Score: 4

The faster version of the min-cut algorithm is very recursive indeed. See figure 2.5 [here](http://valis.cs.uiuc.edu/~sariel/teach/10/a_rand_alg/lec/02_mincut.pdf), or any standard randomized algorithms textbook.

> **Comments:**
> **username_2**: Thats an excellent example as well  

---

