33
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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 (as opposed to Monte Carlo algorithms) or zero-error algorithms, and a related complexity class is ZPP. $\endgroup$
    – Tsuyoshi Ito
    Nov 1, 2010 at 12:29
  • $\begingroup$ @Tsuyoshi: Thanks for your comment. But I'm not aware of Las Vegas-type algorithms for search problems. This is my question. $\endgroup$
    – arnab
    Nov 1, 2010 at 12:37
  • $\begingroup$ If there's a randomized algorithm for finding unique Nash equilibria that would answer your question. $\endgroup$
    – Warren Schudy
    Nov 1, 2010 at 13:32
  • $\begingroup$ Perhaps there's some problem related to birthday attacks (en.wikipedia.org/wiki/Birthday_attack) that would fit your requirements? $\endgroup$
    – Warren Schudy
    Nov 1, 2010 at 13:42

9 Answers 9

Reset to default
23
$\begingroup$

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$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Virtual +1. This is really interesting, will look out for the paper. $\endgroup$
    – András Salamon
    Nov 2, 2010 at 9:55
  • 2
    $\begingroup$ 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 about this. $\endgroup$
    – Tsuyoshi Ito
    Nov 4, 2010 at 20:42
  • 1
    $\begingroup$ I removed the note and made it "community wiki" as per the discussion on the meta thread. $\endgroup$
    – arnab
    Nov 4, 2010 at 22:50
  • $\begingroup$ The meta thread mentioned by arnab can be found here: meta.cstheory.stackexchange.com/q/607/873. $\endgroup$
    – Sadeq Dousti
    Nov 7, 2010 at 21:28
18
$\begingroup$

Do randomized data structures count?

There’s the 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – arnab
    Nov 1, 2010 at 22:35
  • $\begingroup$ Add jump lists to that train of thought. $\endgroup$
    – Raphael
    Nov 3, 2010 at 20:34
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If there are several optimal points, would Kelner-Spielman always return the same point? $\endgroup$
    – Sasho Nikolov
    Oct 13, 2011 at 5:37
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Oct 13, 2011 at 10:02
12
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice!! This definitely qualifies, though I was looking for a more non-trivial example where the improvement in running time is more substantial. $\endgroup$
    – arnab
    Nov 1, 2010 at 22:27
  • $\begingroup$ You don't need the tree structure, this works on an array. $\endgroup$
    – sdcvvc
    Jun 13, 2015 at 9:27
7
$\begingroup$

Polynomial factorization algorithms might be the kind of example you are looking for. The Cantor-Zassenhaus 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 lecture notes.)

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – arnab
    Nov 1, 2010 at 22:20
3
$\begingroup$

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

There is a string matching algorithm (Nebel, 2006) that uses probabilistic ideas. I do know wether this is the fastest approach existing, though, and you apparently need some samples for training.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Median-finding also is faster, but not dramatically so. $\endgroup$
    – Aram Harrow
    Nov 11, 2010 at 0:02
3
$\begingroup$

The following STACS '97 paper might be interesting for your case: The Complexity of Generating Test Instances.

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}$...

Improve this answer
$\endgroup$
2
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ This refers to testing and not finding... $\endgroup$
    – Dana Moshkovitz
    Nov 1, 2010 at 12:25
  • $\begingroup$ I was interested more in search problems. For decision problems, there are Las Vegas algorithms. $\endgroup$
    – arnab
    Nov 1, 2010 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.