<p>Do randomized data structures count?</p>

<p>There’s the <a href="http://en.wikipedia.org/wiki/Skip_list"><strong>skip list</strong></a> which is a sorted associative map data structure.</p>

<p>Its running time for common operations such as insertion, retrieval and deletion are (in the expected case) on par with those in balanced search trees – i.e. $O(\log n)$. However, the data structure is sometimes claimed to have a much better constant factor than search tree implementations when done properly (this relies critically on a good and efficient source of randomness). The better constant factor probably results from the fact that no rebalancing (or any similar operation) has to take place.</p>

CC BY-SA 2.5
2010-11-01T22:35:47.533Z
Thanks!  This definitely does count and is a non-trivial answer to my original question.  I wanted a problem though more analogous to the prime-finding problem, where there are many potential solutions.
arnab
CC BY-SA 2.5
2010-11-03T20:34:08.410Z
Add jump lists to that train of thought.
Raphael
CC BY-SA 2.5
2010-11-01T16:42:58.633Z
2010-11-01T16:42:58.633Z
Konrad Rudolph
<p>How about Kelner and Spielman's randomized polynomial-time simplex algorithm? It finds the optimal vertex of a linear program. No deterministic simplex algorithm is known which is proven to run in polynomial time, and for many of them, pathological instances can be constructed that make the algorithm take exponential time.</p>

<p>Of course, there are polynomial-time interior-point algorithms, so it's not exactly what you're looking for.</p>

CC BY-SA 3.0
2011-10-13T05:37:19.273Z
If there are several optimal points, would Kelner-Spielman always return the same point?
Sasho Nikolov
CC BY-SA 3.0
2011-10-13T10:02:47.057Z
Generic linear programs have only one optimal point, so using perturbation, a variant of Kelner-Spielman could be made that always returns the same optimal point.
Peter Shor 
CC BY-SA 2.5
2010-11-02T02:25:09.597Z
2010-11-02T02:25:09.597Z
Peter Shor 
<p>Consider a complete binary tree with all $2^n$ leaves containing 0, except one leaf that contains 1.  The task is to find the leaf that contains 1.  Against any deterministic search algorithm it is possible to construct an infinite family of trees (one for each $n$) for which the algorithm has to check every leaf.  So for this worst-case family the deterministic algorithm has expected runtime $2^n$.</p>

<p>Now consider an algorithm that randomly chooses the first leaf uniformly at random, and then checks all successive leaves deterministically (wrapping around to the beginning).  This will find the 1 after examining half of all leaves, on average.  So the randomized algorithm has expected runtime $2^{n-1}$.</p>

<p>Does this qualify?</p>

CC BY-SA 3.0
2015-06-13T09:27:06.547Z
You don't need the tree structure, this works on an array.
sdcvvc
CC BY-SA 2.5
2010-11-01T22:27:52.320Z
Nice!!  This definitely qualifies, though I was looking for a more non-trivial example where the improvement in running time is more substantial.
arnab
CC BY-SA 2.5
2010-11-01T16:33:05.520Z
2010-11-01T16:33:05.520Z
András Salamon
<p>Polynomial factorization algorithms might be the kind of example you are looking for. The  <a href="http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm">Cantor-Zassenhaus algorithm</a> uses randomness to compute the (unique upto scaling) irreducible polynomial factors of a given univariate polynomial over a finite field $\mathbb{F}_p$ in time polynomial in the size of the input and $\log p$. If you really want the problem to have a unique answer, you can ask for the monic irreducible prime factors of a monic polynomial. As far as I know, it is not known how to factorize in deterministic polynomial time unless $p$ is guaranteed to be small.</p>

<p>By the way, the above can be made a zero-error algorithm, since we know how to test for irreducibility of a polynomial deterministically in time polynomial in the degree of the polynomial and $\log p$. (See <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/algcomp/lecture11.pdf">these</a> lecture notes.)</p>

CC BY-SA 2.5
2010-11-01T14:51:41.470Z
2010-11-01T15:10:05.067Z
2010-11-01T15:10:05.067Z
Srikanth
<p>There was a polymath project addressing a related question:
<a href="http://michaelnielsen.org/polymath1/index.php?title=Finding_primes">http://michaelnielsen.org/polymath1/index.php?title=Finding_primes</a></p>

CC BY-SA 2.5
2010-11-01T22:20:38.480Z
Yes, this was a source of motivation for my asking the question.  I don't think they explicitly mentioned this question in the polymath project.
arnab
CC BY-SA 2.5
2010-11-01T12:15:25.377Z
2010-11-01T12:15:25.377Z
Anthony Leverrier
<p>Regarding your first question, I thought of Quicksort first but that should be obvious. </p>

<p>There is a string matching algorithm (<a href="http://wwwagak.informatik.uni-kl.de/staff/nebel/www_horspool/www_horspool.ps" rel="nofollow">Nebel, 2006</a>) that uses probabilistic ideas. I do know wether this is the fastest approach existing, though, and you apparently need some samples for training.</p>

CC BY-SA 2.5
2010-11-11T00:02:44.433Z
Median-finding also is faster, but not dramatically so.
Aram Harrow
CC BY-SA 2.5
2010-11-01T12:42:12.113Z
2010-11-01T12:42:12.113Z
Raphael
<p>The following STACS '97 paper might be interesting for your case: <a href="http://www.springerlink.com/content/mh2560g8kx54r315/" rel="nofollow">The Complexity of Generating Test Instances</a>.</p>

<p>Abstract: Recently, Watanabe proposed a new framework for testing the correctness and average case behavior of algorithms that purport to solve a given NP search problem efficiently on average. The idea is to randomly generate certified instances in a way that resembles the underlying distribution. We discuss this approach and show that test instances can be generated for every NP search problem with non-adaptive queries to an NP oracle. Further, we introduce Las Vegas as well as Monte Carlo types of test instance generators and show that these generators can be used to find out whether an algorithm is correct and efficient on average. In fact, it is not hard to construct Monte Carlo generators for all RP search problems as well as Las Vegas generators for all ZPP search problems. On the other hand, we prove that Monte Carlo generators can only exist for problems in co-AM.</p>

<p>Specially, take a look at page 384, under Corollary 12: </p>

<blockquote>
  <p>It is not hard to construct a Las Vegas generator for any $\rm{ZPP}$ search problem, i.e. for any $\rm{RP}$ search problem whose domain is in $\rm{ZPP}$. On the other hand, Las Vegas generators can only exist for $\rm{NP}$ problems whose domain belongs to $\rm{NP} \cap \rm{coNP}$...</p>
</blockquote>

CC BY-SA 2.5
2010-11-01T14:23:19.603Z
2010-11-01T14:23:19.603Z
Sadeq Dousti
<p>Before [AKS], Primality had coRP and RP algorithms (Miller-Rabin for coRP, Adleman-Huang for RP). A natural zero error extension would be to run both simultaneously until you push the error down to $\frac{1}{n^c}$ or so, and then run the brute-force algorithm. The expected running time would then remain $\text{polylog}(n)$.</p>

CC BY-SA 2.5
2010-11-01T12:25:45.847Z
This refers to testing and not finding...
Dana Moshkovitz
CC BY-SA 2.5
2010-11-01T12:26:02.660Z
I was interested more in search problems.  For decision problems, there are Las Vegas algorithms.
arnab
CC BY-SA 2.5
2010-11-01T10:41:39.207Z
2010-11-01T10:41:39.207Z
Ramprasad
<p>Shafi Goldwasser communicated to me that she and coauthors have been investigating exactly such algorithms for number-theoretic problems!  The following is known:</p>

<ol>
<li><p>Lenstra has shown that there is such an algorithm for finding a quadratic non-residue mod a given prime.</p></li>
<li><p>Gat and Goldwasser have shown that there is such an algorithm for finding a generator of $\mathbb{Z}_p^*$, where $p$ is a given prime of the form $2q + 1$ for a prime $q$.</p></li>
</ol>

<p>(I don't know of citable references.) There is also ongoing research on the question I asked about finding a prime between $n$ and $2n$.</p>

<p>EDIT: The paper by Gat and Goldwasser is now published: <a href="http://eccc.hpi-web.de/report/2011/136/">http://eccc.hpi-web.de/report/2011/136/</a>. This paper though doesn't resolve the question of finding a prime between $n$ and $2n$. </p>

CC BY-SA 2.5
2010-11-02T09:55:37.697Z
Virtual +1.  This is really interesting, will look out for the paper.
András Salamon
CC BY-SA 2.5
2010-11-04T20:42:11.523Z
In spite of the note, I upvoted this answer simply because this is a good answer.  I do not think that there is anything wrong with upvoting a good answer posted for someone else.  I started a [discussion on Meta](http://meta.cstheory.stackexchange.com/questions/607/upvoting-an-answer-provided-by-someone-else) about this.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-04T22:50:38.477Z
I removed the note and made it "community wiki" as per the discussion on the meta thread.
arnab
CC BY-SA 2.5
2010-11-07T21:28:40.983Z
The meta thread mentioned by arnab can be found here: http://meta.cstheory.stackexchange.com/q/607/873.
Sadeq Dousti
CC BY-SA 3.0
2010-11-01T23:32:35.350Z
2011-10-12T22:31:54.103Z
2011-10-12T22:31:54.103Z
arnab
<p>Is there an interesting example of a randomized algorithm for a search problem that always outputs the <em>same</em> (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?</p>

<p>In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n.  There's no known polynomial time deterministic algorithm.  There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">prime number theorem</a>.  But is there an algorithm of the above kind whose expected running time is intermediate between the two?</p>

<p>EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are <em>many</em> possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness.  I realize that the question is probably not fully specified...</p>

CC BY-SA 2.5
2010-11-01T12:29:28.617Z
To give you some search keywords, randomized algorithms which always produces the correct answer (and uses randomness for shorter running time) are called [Las Vegas algorithms](http://en.wikipedia.org/wiki/Las_Vegas_algorithm) (as opposed to Monte Carlo algorithms) or zero-error algorithms, and a related complexity class is [ZPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:Z#zpp).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-01T12:37:53.770Z
@Tsuyoshi: Thanks for your comment.  But I'm not aware of Las Vegas-type algorithms for search problems.  This is my question.
arnab
CC BY-SA 2.5
2010-11-01T13:32:10.680Z
If there's a randomized algorithm for finding unique Nash equilibria that would answer your question.
Warren Schudy
CC BY-SA 2.5
2010-11-01T13:42:28.203Z
Perhaps there's some problem related to birthday attacks (http://en.wikipedia.org/wiki/Birthday_attack) that would fit your requirements?
Warren Schudy
<ds.algorithms><randomized-algorithms>
Randomized algorithm that "looks" deterministic?
arnab
# Randomized algorithm that "looks" deterministic?

(Asked by: username_0 on 2010-11-01)

Is there an interesting example of a randomized algorithm for a search problem that always outputs the *same* (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n. There's no known polynomial time deterministic algorithm. There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem). But is there an algorithm of the above kind whose expected running time is intermediate between the two?

EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are *many* possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness. I realize that the question is probably not fully specified...

**Tags:** ds.algorithms, randomized-algorithms

> **Comments:**
> **username_1**: To give you some search keywords, randomized algorithms which always produces the correct answer (and uses randomness for shorter running time) are called [Las Vegas algorithms](http://en.wikipedia.org/wiki/Las_Vegas_algorithm) (as opposed to Monte Carlo algorithms) or zero-error algorithms, and a related complexity class is [ZPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo:Z#zpp).  
> **username_0**: @Tsuyoshi: Thanks for your comment.  But I'm not aware of Las Vegas-type algorithms for search problems.  This is my question.  
> **username_2**: If there's a randomized algorithm for finding unique Nash equilibria that would answer your question.  
> **username_2**: Perhaps there's some problem related to birthday attacks (http://en.wikipedia.org/wiki/Birthday_attack) that would fit your requirements?  

---

## 9 answers

### Answer by username_0 on 2010-11-01. Score: 23 | Accepted answer

Shafi Goldwasser communicated to me that she and coauthors have been investigating exactly such algorithms for number-theoretic problems! The following is known:

1. Lenstra has shown that there is such an algorithm for finding a quadratic non-residue mod a given prime.
2. Gat and Goldwasser have shown that there is such an algorithm for finding a generator of $\mathbb{Z}\_p^\*$, where $p$ is a given prime of the form $2q + 1$ for a prime $q$.

(I don't know of citable references.) There is also ongoing research on the question I asked about finding a prime between $n$ and $2n$.

EDIT: The paper by Gat and Goldwasser is now published: <http://eccc.hpi-web.de/report/2011/136/>. This paper though doesn't resolve the question of finding a prime between $n$ and $2n$.

> **Comments:**
> **username_7**: Virtual +1.  This is really interesting, will look out for the paper.  
> **username_1**: In spite of the note, I upvoted this answer simply because this is a good answer.  I do not think that there is anything wrong with upvoting a good answer posted for someone else.  I started a [discussion on Meta](http://meta.cstheory.stackexchange.com/questions/607/upvoting-an-answer-provided-by-someone-else) about this.  
> **username_0**: I removed the note and made it "community wiki" as per the discussion on the meta thread.  
> **username_12**: The meta thread mentioned by username_0 can be found here: http://meta.cstheory.stackexchange.com/q/607/873.  

---

### Answer by username_3 on 2010-11-01. Score: 18

Do randomized data structures count?

There’s the [**skip list**](http://en.wikipedia.org/wiki/Skip_list) which is a sorted associative map data structure.

Its running time for common operations such as insertion, retrieval and deletion are (in the expected case) on par with those in balanced search trees – i.e. $O(\log n)$. However, the data structure is sometimes claimed to have a much better constant factor than search tree implementations when done properly (this relies critically on a good and efficient source of randomness). The better constant factor probably results from the fact that no rebalancing (or any similar operation) has to take place.

> **Comments:**
> **username_0**: Thanks!  This definitely does count and is a non-trivial answer to my original question.  I wanted a problem though more analogous to the prime-finding problem, where there are many potential solutions.  
> **username_4**: Add jump lists to that train of thought.  

---

### Answer by username_5 on 2010-11-02. Score: 13

How about Kelner and Spielman's randomized polynomial-time simplex algorithm? It finds the optimal vertex of a linear program. No deterministic simplex algorithm is known which is proven to run in polynomial time, and for many of them, pathological instances can be constructed that make the algorithm take exponential time.

Of course, there are polynomial-time interior-point algorithms, so it's not exactly what you're looking for.

> **Comments:**
> **username_6**: If there are several optimal points, would Kelner-Spielman always return the same point?  
> **username_5**: Generic linear programs have only one optimal point, so using perturbation, a variant of Kelner-Spielman could be made that always returns the same optimal point.  

---

### Answer by username_7 on 2010-11-01. Score: 12

Consider a complete binary tree with all $2^n$ leaves containing 0, except one leaf that contains 1. The task is to find the leaf that contains 1. Against any deterministic search algorithm it is possible to construct an infinite family of trees (one for each $n$) for which the algorithm has to check every leaf. So for this worst-case family the deterministic algorithm has expected runtime $2^n$.

Now consider an algorithm that randomly chooses the first leaf uniformly at random, and then checks all successive leaves deterministically (wrapping around to the beginning). This will find the 1 after examining half of all leaves, on average. So the randomized algorithm has expected runtime $2^{n-1}$.

Does this qualify?

> **Comments:**
> **username_0**: Nice!!  This definitely qualifies, though I was looking for a more non-trivial example where the improvement in running time is more substantial.  
> **username_8**: You don't need the tree structure, this works on an array.  

---

### Answer by username_9 on 2010-11-01. Score: 7

Polynomial factorization algorithms might be the kind of example you are looking for. The [Cantor-Zassenhaus algorithm](http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm) uses randomness to compute the (unique upto scaling) irreducible polynomial factors of a given univariate polynomial over a finite field $\mathbb{F}\_p$ in time polynomial in the size of the input and $\log p$. If you really want the problem to have a unique answer, you can ask for the monic irreducible prime factors of a monic polynomial. As far as I know, it is not known how to factorize in deterministic polynomial time unless $p$ is guaranteed to be small.

By the way, the above can be made a zero-error algorithm, since we know how to test for irreducibility of a polynomial deterministically in time polynomial in the degree of the polynomial and $\log p$. (See [these](http://www.cmi.ac.in/~ramprasad/lecturenotes/algcomp/lecture11.pdf) lecture notes.)


---

### Answer by username_10 on 2010-11-01. Score: 6

There was a polymath project addressing a related question:
<http://michaelnielsen.org/polymath1/index.php?title=Finding_primes>

> **Comments:**
> **username_0**: Yes, this was a source of motivation for my asking the question.  I don't think they explicitly mentioned this question in the polymath project.  

---

### Answer by username_4 on 2010-11-01. Score: 3

Regarding your first question, I thought of Quicksort first but that should be obvious.

There is a string matching algorithm ([Nebel, 2006](http://wwwagak.informatik.uni-kl.de/staff/nebel/www_horspool/www_horspool.ps)) that uses probabilistic ideas. I do know wether this is the fastest approach existing, though, and you apparently need some samples for training.

> **Comments:**
> **username_11**: Median-finding also is faster, but not dramatically so.  

---

### Answer by username_12 on 2010-11-01. Score: 3

The following STACS '97 paper might be interesting for your case: [The Complexity of Generating Test Instances](http://www.springerlink.com/content/mh2560g8kx54r315/).

Abstract: Recently, Watanabe proposed a new framework for testing the correctness and average case behavior of algorithms that purport to solve a given NP search problem efficiently on average. The idea is to randomly generate certified instances in a way that resembles the underlying distribution. We discuss this approach and show that test instances can be generated for every NP search problem with non-adaptive queries to an NP oracle. Further, we introduce Las Vegas as well as Monte Carlo types of test instance generators and show that these generators can be used to find out whether an algorithm is correct and efficient on average. In fact, it is not hard to construct Monte Carlo generators for all RP search problems as well as Las Vegas generators for all ZPP search problems. On the other hand, we prove that Monte Carlo generators can only exist for problems in co-AM.

Specially, take a look at page 384, under Corollary 12:

> It is not hard to construct a Las Vegas generator for any $\rm{ZPP}$ search problem, i.e. for any $\rm{RP}$ search problem whose domain is in $\rm{ZPP}$. On the other hand, Las Vegas generators can only exist for $\rm{NP}$ problems whose domain belongs to $\rm{NP} \cap \rm{coNP}$...


---

### Answer by username_13 on 2010-11-01. Score: 2

Before [AKS], Primality had coRP and RP algorithms (Miller-Rabin for coRP, Adleman-Huang for RP). A natural zero error extension would be to run both simultaneously until you push the error down to $\frac{1}{n^c}$ or so, and then run the brute-force algorithm. The expected running time would then remain $\text{polylog}(n)$.

> **Comments:**
> **username_14**: This refers to testing and not finding...  
> **username_0**: I was interested more in search problems.  For decision problems, there are Las Vegas algorithms.  

---

