11
$\begingroup$

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 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. Note that SivaKumar used Nisan's Pseudo-random generator to derandomize these problems.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 24 '10 at 4:16
  • $\begingroup$ You should make this an answer ! $\endgroup$ – Suresh Venkat Sep 24 '10 at 4:20
6
$\begingroup$

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 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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shiva Kintali Sep 24 '10 at 9:42
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shiva Kintali Sep 24 '10 at 9:33
4
$\begingroup$

The faster version of the min-cut algorithm is very recursive indeed. See figure 2.5 here, or any standard randomized algorithms textbook.

$\endgroup$
  • $\begingroup$ Thats an excellent example as well $\endgroup$ – Suresh Venkat Sep 25 '10 at 5:58

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.