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.
Randomized algorithms using a stack
randomness;derandomization
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 ? 