<p>Once you are not just talking about poly-time but rather look at the many models of computation we study, there are examples everywhere:</p>

<p>In Logspace: Un-directed ST connectivity (in RL since 1979, and in L only since 2005)</p>

<p>In NC: Finding a perfect matching in a bipartite graph in parallel (in RNC and still not known to be in NC)</p>

<p>In interactive proofs: deterministic ones give NP, while randomized ones can do PSPACE.  Related: checking a proof deterministically requires looking at all the proof, while PCP proofs allow you to check only a constant number of bits.</p>

<p>In Algorithmic Mechanism Design: many randomized truthful approximation mechanisms with no deterministic counterpart.</p>

<p>In Communication complexity: the equality function requires linear communication deterministically but logarithmic (or, depending on exact model, constant) communication randomly.</p>

<p>In decision trees: evaluating an and-or tree requires linear queries deterministically but much less with randomization.  This is essentially equivalent to alpha-beta pruning which gives a randomized sub-linear algorithm for game-tree evaluation.</p>

<p>In streaming models, distributed computing models: see previous answers.</p>

CC BY-SA 3.0
2012-11-20T23:52:47.220Z
2012-11-20T23:52:47.220Z
Noam
<p><strong>Most streaming algorithms</strong></p>
<p>In the streaming model of computation (<a href="https://www.tau.ac.il/%7Enogaa/PDFS/amsz4.pdf" rel="nofollow noreferrer">AMS</a>, <a href="http://algo.research.googlepages.com/eight.ps" rel="nofollow noreferrer">book</a>), an algorithm processes an online sequence of updates and is restricted to keep only sublinear space. At any point in time, the algorithm should be able to answer a query.</p>
<p>For many problems there exist sublinear space randomized streaming algorithms while provably no deterministic algorithm can solve the problem in sublinear space. This is related to gaps between randomized and deterministic communication complexity. A simple example is the <em>distinct count</em> problem: at each time step <span class="math-container">$t$</span> the algorithm is given an integer <span class="math-container">$i_t \in [n]$</span>, and it should be able to approximate <span class="math-container">$D_m = |\{i_t: t = 1\ldots m\}|$</span>, i.e. the number of distinct integers seen up to time step <span class="math-container">$m$</span>. It's relatively easy to show that any deterministic algorithm achieving constant approximation must use <span class="math-container">$\Omega(n)$</span> space (see e.g. <a href="https://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec9/lec9.pdf" rel="nofollow noreferrer">lecture notes</a> by Piotr Indyk). On the other hand the <a href="http://algo.inria.fr/flajolet/Publications/FlMa85.pdf" rel="nofollow noreferrer">clever sampling algorithm</a> of Flajolet and Martin (simple analysis with limited randomness in the AMS paper linked above) achieves constant approximation in <span class="math-container">$O(\log n)$</span> bits. The <a href="https://web.archive.org/web/20110107060020/http://www.almaden.ibm.com/cs/people/dpwoodru/knw11.pdf" rel="nofollow noreferrer">latest work</a> on the problem gives an optimal <span class="math-container">$O(\frac{1}{\epsilon^2} + \log n)$</span> algorithm that computes an <span class="math-container">$1\pm \epsilon$</span> approximation.</p>

CC BY-SA 4.0
2012-11-20T20:26:45.523Z
2022-07-15T13:59:32.173Z
2022-07-15T13:59:32.173Z
Sasho Nikolov
<p><strong>Majority problem in a query model.</strong></p>

<p><strong>Problem</strong>. We are given a set of $n$ balls colored with two or more colors. The goal is to ﬁnd a ball of the majority color (i.e., a color that occurs more than n/2 times) assuming such a color exists, using queries of the form "Does ball $i$ and ball $j$ have the same color?". The strategy must be oblivious, i.e., queries cannot depend on the results of previous queries.</p>

<p><strong>Randomized Algorithm</strong>. Pick a random ball and check if more than $n/2$ balls have the same color. This algorithm runs in $O(n)$ time in expectation.</p>

<p><strong>Deterministic $O(n)$ algorithm</strong> is quite non-trivial and is a nice application of expanders. </p>

<p>F. R. K. Chung, R. L. Graham, J. Mao, and A. C. Yao, Oblivious and adaptive strategies for the Majority and Plurality problems, <em>Proc. COCOON 2005</em>, pp. 329–338.</p>

CC BY-SA 3.0
2012-11-21T06:19:44.447Z
2013-05-08T04:58:26.817Z
2013-05-08T04:58:26.817Z
Jagadish
<p>Finding a <strong>maximal independent set in a distributed network</strong> of $n$ nodes with maximum degree $\Delta$. There's a known lower bound [3] of $\min(\Omega(\log\Delta),\Omega(\sqrt{\log n}))$ that holds for randomized and deterministic algorithms.</p>

<p>The following is a simple randomized distributed algorithm [1] that proceeds in synchronous <em>rounds</em>. (In a round, every node $u$ can perform some local computation and send messages to its neighbors. These messages are guaranteed to be received before the start of the next round.)</p>

<ol>
<li>In every round, each active node $u$ marks itself with probability $1/d_u$ where $d_u&gt;0$ is the degree of $u$; if $d_u=0$, $u$ simply enters the independent set. (Initially, every node is active.)</li>
<li>If $u$ is the only marked node in its neighborhood, $u$ enters the independent set, deactivates itself and notifies all of its neighbors to deactivate themselves. The degrees of the remaining active nodes are decreased accordingly, i.e., all edges to deactivated nodes are removed. </li>
<li>Otherwise, if there is some neighboring node $v$ that is also marked, the lower degree vertex unmarks itself and remains active.</li>
</ol>

<p>It can be shown that this algorithm terminates in $O(\log n)$ rounds with high probability, by arguing that half of the remaining edges are deleted in every round. In contrast, the fastest known deterministic distributed algorithm [2] takes $O(n^{1/\sqrt{\log n}})$ rounds and is considerably more complicated.</p>

<hr>

<p>[1] Michael Luby: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15(4): 1036-1053 (1986)
<a href="http://dx.doi.org/10.1137/0215074">http://dx.doi.org/10.1137/0215074</a></p>

<p>[2] Alessandro Panconesi, Aravind Srinivasan: On the Complexity of Distributed Network Decomposition. J. Algorithms 20(2): 356-374 (1996)
<a href="http://dx.doi.org/10.1006/jagm.1996.0017">http://dx.doi.org/10.1006/jagm.1996.0017</a></p>

<p>[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
<a href="http://arxiv.org/abs/1011.5470">http://arxiv.org/abs/1011.5470</a></p>

CC BY-SA 3.0
2013-05-08T15:15:55.593Z
A recent algorithm (at PODC 2013), inspired by biological systems, achieves performance as good as Luby's by using a simple local feedback mechanism.  http://arxiv.org/abs/1211.0235
András Salamon
CC BY-SA 3.0
2012-11-20T14:14:17.243Z
2012-11-20T17:28:59.167Z
2012-11-20T17:28:59.167Z
Peter
<h2>Leader Election in an Anonymous Ring of Processes</h2>

<p>Suppose that you have a ring network of processes that do not have ids and that communicate by message passing. Initially, every process is in the same state. 
You want to design a distributed algorithm such that eventually exactly $1$ process enters the <em>elected</em> state and all other processes enter the <em>non-elected</em> state. This is the so called leader election problem which is one of the fundamental symmetry breaking tasks in a distributed system and has many applications.</p>

<p>There's a simple argument (e.g. [1]) that there is no <em>deterministic</em> leader election algorithm for an anonymous ring.</p>

<p><strong>Model:</strong> We assume that the computation advances in synchronous rounds where, in each round, every process performs some local computation, sends messages to its neighbors in the ring, and receives messages from its neighbors.</p>

<p>For the sake of a contradiction, let's assume that there is such a deterministic leader election algorithm $A$.
It is sufficient to show that, at the start of any round $r\ge 0$, all processes are in the same state, since this implies that there cannot be exactly $1$ process in the <em>elected</em> state.
Since processes do not have ids and the network is symmetric, every process is in the same initial state, which provides the induction base.</p>

<p>For the induction step, consider some round $r\ge 0$ and assume that every process is in the same state at the start of round $r$. Therefore, since algorithm $A$ is deterministic, every process performs exactly the same computation and sends exactly the same messages during round $r$. This in turn implies that every process receives exactly the same messages during $r$ and, by the start of round $r+1$, is in the same state. Thus, no such algorithm $A$ can exist.</p>

<p>If $A$ is a randomized algorithm on the other hand and processes know the size of the ring $n$, there's an easy way to break symmetry, by generating a random id from the range $[1,n^4]$, which will result in unique ids for all processes with high probability. A simple and naive algorithm proceeds by letting every process send its id along the ring and instruct processes to forward only messages containing the largest id seen so far. This guarantees that only the process who generated the largest id will  receive its own message once it has traversed the entire ring and elect itself as the leader. </p>

<hr>

<p>[1] Dana Angluin: Local and Global Properties in Networks of Processors (Extended Abstract). STOC 1980: 82-93.
<a href="http://doi.acm.org/10.1145/800141.804655">http://doi.acm.org/10.1145/800141.804655</a></p>

CC BY-SA 3.0
2012-11-20T18:03:07.477Z
2012-11-20T18:03:07.477Z
Peter
<p>Finding square roots modulo prime number:</p>
<p><a href="https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm</a></p>

CC BY-SA 4.0
2022-08-16T21:43:17.913Z
2022-08-16T21:43:17.913Z
mercury0114
<p>Finding a 2-approximate weighted vertex cover is known to be in RNC [1].  I don't think it is known to be in NC. That is, the problem has a randomized poly-log-time poly-processor algorithm, but I don't think it is known to have a deterministic poly-log-time poly-processor algorithm.</p>
<p>[1] <a href="https://dx.doi.org/10.1007/s00446-011-0127-7" rel="nofollow noreferrer">https://dx.doi.org/10.1007/s00446-011-0127-7</a></p>

CC BY-SA 4.0
2022-07-16T18:59:52.620Z
2022-07-16T18:59:52.620Z
Neal Young
<p>This problem defined in 1982 by Papadimitriou and Yannakakis:</p>
<p>Exact Perfect Matching problem</p>
<p>Input: A graph G, with each edge colored red or blue, and integer k.</p>
<p>Problem: Decide whether there exists a perfect matching M in G with exactly k red edges</p>
<p>Exact Perfect Matching lies in the complexity class <span class="math-container">$RP$</span> since it has a randomized polynomial time algorithm (given by Mulmuley, Vazirani and Vazirani ). Therefor it is unlikely to be <span class="math-container">$NP$</span>-hard.</p>

CC BY-SA 4.0
2022-08-18T17:05:09.663Z
2022-08-18T17:05:09.663Z
Mohammad Al-Turkistany
<p><strong>Sorting nuts and bolts</strong></p>

<p>The following problem was suggested by Rawlins in 1992:  Suppose you are given a collection of n nuts and n bolts.  Each bolt fits exactly one nut, and otherwise, the nuts and bolts have distinct sizes.  The sizes are too close to allow direct comparison between pairs of bolts or pairs of nuts.  However, you can compare any nut to any bolt by trying to screw them together; in constant time, you will discover whether the bolt is too large, too small, or just right for the nut.  Your task is to discover which bolt fits each nut, or equivalently, to sort the nuts and bolts by size.</p>

<p>A straightforward variant of randomized quicksort solves the problem in $O(n \log n)$ time with high probability.  Pick a random bolt; use it to partition the nuts; use the matching nut to partition the bolts; and recurse.  However, finding a deterministic algorithm that even runs in $o(n^2)$ is nontrivial.  Deterministic $O(n\log n)$-time algorithms were finally found in 1995 by Bradford and independently by Komlós, Ma, and Szemerédi.  Under the hood, both algorithms use variants of the AKS parallel sorting network, so the hidden constant in the $O(n\log n)$ time bound is quite large; the hidden constant for the randomized algorithm is 4.</p>

<ul>
<li>Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar, and Rafail Ostrovsky. Matching nuts and bolts. <em>Proc. 5th Ann. ACM-SIAM Symp. Discrete Algorithms</em>, 690–696, 1994.</li>
<li>Noga Alon, Phillip G. Bradford, and Rudolf Fleischer. Matching nuts and bolts faster. <em>Inform. Proc. Lett.</em> 59(3):123–127, 1996.</li>
<li>Phillip G. Bradford. Matching nuts and bolts optimally. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. <a href="http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025">http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025</a></li>
<li>Phillip G. Bradford and Rudolf Fleischer. Matching nuts and bolts faster.  <em>Proc. 6th. Int. Symp. Algorithms Comput.</em>, 402–408, 1995. Lecture Notes Comput. Sci. 1004.</li>
<li>János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in $O(n\log n)$ time. <em>SIAM J. Discrete Math.</em> 11(3):347–372, 1998.</li>
<li>Gregory J. E. Rawlins. <em>Compared To What? : An Introduction to The Analysis of Algorithms</em>. Computer Science Press/W. H. Freeman, 1992.</li>
</ul>

CC BY-SA 3.0
2012-11-24T21:40:55.187Z
This is a beautiful example, but it's an oracle problem. Is there some way to remove the oracle from it?
Peter Shor 
CC BY-SA 3.0
2012-11-29T23:06:22.380Z
Got a link to the 98 Szemeredi paper? How is this hard? In parallel compare each bolt to a unique nut and put each pair in sorted order; removing matched elements.  In log(n) steps merge the sorted nbnbnbnbnb sequences, kicking out matches as they arise.  EDIT: Yeah the noncomparability of nnn and bbbb strings is annoying on the merge step.
Chad Brewbaker
CC BY-SA 3.0
2012-11-30T05:29:13.713Z
@ChadBrewbaker  Suppose in every pair but one, the bolt is smaller than the nut.  (Yes, this is possible.)  Now what does your algorithm do?  In other words, "annoying" = "the whole problem".
Jeffε
CC BY-SA 3.0
2012-11-30T20:08:18.830Z
I was looking for the Szemeredi paper and thinking out loud how it is hard. Yes, I concur that a merge based approach is nontrivial; but Vishkin's papers on parallel graph connectivity leave a gut feeling it is not impossible.
Chad Brewbaker
CC BY-SA 3.0
2012-11-30T20:14:25.697Z
With each comparison from a nut and bolt you get a directed edge added to the graph or a match which removes both vertices. The goal would be to merge connected components in such a way that they collapse all matches between them with a linear amount of work and keep the storage size of edges in a connected component bounded to linear space.
Chad Brewbaker
CC BY-SA 3.0
2012-11-30T23:11:37.957Z
In fact, there is a **randomized** mergesort solution, which I've never seen written down.  Flip 2n coins to split the nuts and bolts into two subsets; recursively sort the subsets as as much as possible; merge the two "sorted" lists.  The merge step only needs $O(n)$ expected time, because the expected length of any string of incomparable nuts or bolts is constant (even deep in the recursion).  With high probability, the recursion ends after $O(\log n)$ levels.
Jeffε
CC BY-SA 3.0
2012-11-20T16:10:18.767Z
2012-11-21T01:08:51.360Z
2012-11-21T01:08:51.360Z
Jeffε
<p>I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most prominently</p>

<ul>
<li>Randomized Quicksort (and related geometric algorithms, e.g. for convex hulls)</li>
<li>Randomized Mincut</li>
<li>Polynomial Identity Testing</li>
<li>Klee's Measure problem</li>
</ul>

<p>Among these, only polynomial identity testing seems to be really hard without the use of randomness. </p>

<p>Do you know more examples of problems where a randomized solution is very elegant or very efficient, but deterministic solutions are not? Ideally, the problems should be easy to motivate for laymen (unlike e.g. polynomial identity testing).</p>

CC BY-SA 3.0
2012-11-20T13:39:36.313Z
Another example is primality testing.  The Miller–Rabin and Solovay–Strassen probabilistic primality tests are very simple and efficient. It was a long standing open problem to find an efficient deterministic primality test, which was solved by Agrawal, Kayal and Saxena. The AKS test is a deterministic polynomial-test primality test. However, it is not as simple and not so efficient as probabilistic tests.
Yury
CC BY-SA 3.0
2012-11-20T16:00:12.283Z
Randomized selection (median finding) is somewhat easier than deterministic.  Randomized algorithms for approximately solving packing and covering LPs are faster (in worst-case) than their deterministic counterparts ([KY07](http://scholar.google.com/scholar?cluster=927118074980911873&hl=en&as_sdt=0,5&as_vis=1), [GK95](http://scholar.google.com/scholar?cluster=3647150107566098261&hl=en&as_sdt=0,5&as_vis=1)). Many online problems have randomized alg's that are more competitive than any deterministic algorithm [FK91](http://scholar.google.com/scholar?cluster=3119858358413388303&hl=en&as_sdt=0,5).
Neal Young
CC BY-SA 3.0
2012-11-20T17:00:17.157Z
Computing the volume of a convex body in high dimensions admits a $(1+\epsilon)$-approximation via randomization. It is known that no deterministic algorithm can give a good approximation. Hence randomization is essential here.
Chandra Chekuri
CC BY-SA 3.0
2012-11-20T17:28:24.927Z
@ChandraChekuri that's a good comment and would be an even better answer :)
Suresh Venkat
CC BY-SA 3.0
2012-11-20T18:30:25.737Z
@ChandraChekuri in the oracle model, otherwise $\mathsf{BPP} \neq \mathsf{P}$
Sasho Nikolov
CC BY-SA 3.0
2012-11-21T01:10:15.520Z
Yury, Neal, and Chandra's comments should be answers!
Jeffε
CC BY-SA 3.0
2012-11-24T05:23:20.117Z
See also [http://cstheory.stackexchange.com/questions/11738/does-randomness-buy-us-anything-inside-p](http://cstheory.stackexchange.com/questions/11738/does-randomness-buy-us-anything-inside-p).
Neal Young
CC BY-SA 4.0
2022-08-17T09:48:18.110Z
Could also approximation of the permanent be an example?
kostrykin
<ds.algorithms><randomized-algorithms><derandomization>
Efficient and simple randomized algorithms where determinism is difficult
adrianN
# Efficient and simple randomized algorithms where determinism is difficult

(Asked by: username_0 on 2012-11-20)

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most prominently

* Randomized Quicksort (and related geometric algorithms, e.g. for convex hulls)
* Randomized Mincut
* Polynomial Identity Testing
* Klee's Measure problem

Among these, only polynomial identity testing seems to be really hard without the use of randomness.

Do you know more examples of problems where a randomized solution is very elegant or very efficient, but deterministic solutions are not? Ideally, the problems should be easy to motivate for laymen (unlike e.g. polynomial identity testing).

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

> **Comments:**
> **username_1**: Another example is primality testing.  The Miller–Rabin and Solovay–Strassen probabilistic primality tests are very simple and efficient. It was a long standing open problem to find an efficient deterministic primality test, which was solved by Agrawal, Kayal and Saxena. The AKS test is a deterministic polynomial-test primality test. However, it is not as simple and not so efficient as probabilistic tests.  
> **username_2**: Randomized selection (median finding) is somewhat easier than deterministic.  Randomized algorithms for approximately solving packing and covering LPs are faster (in worst-case) than their deterministic counterparts ([KY07](http://scholar.google.com/scholar?cluster=927118074980911873&hl=en&as_sdt=0,5&as_vis=1), [GK95](http://scholar.google.com/scholar?cluster=3647150107566098261&hl=en&as_sdt=0,5&as_vis=1)). Many online problems have randomized alg's that are more competitive than any deterministic algorithm [FK91](http://scholar.google.com/scholar?cluster=3119858358413388303&hl=en&as_sdt=0,5).  
> **username_3**: Computing the volume of a convex body in high dimensions admits a $(1+\epsilon)$-approximation via randomization. It is known that no deterministic algorithm can give a good approximation. Hence randomization is essential here.  
> **username_4**: @ChandraChekuri that's a good comment and would be an even better answer :)  
> **username_5**: @ChandraChekuri in the oracle model, otherwise $\mathsf{BPP} \neq \mathsf{P}$  
> **username_6**: username_1, Neal, and Chandra's comments should be answers!  
> **username_2**: See also [http://cstheory.stackexchange.com/questions/11738/does-randomness-buy-us-anything-inside-p](http://cstheory.stackexchange.com/questions/11738/does-randomness-buy-us-anything-inside-p).  
> **username_7**: Could also approximation of the permanent be an example?  

---

## 9 answers

### Answer by username_6 on 2012-11-20. Score: 41 | Accepted answer

**Sorting nuts and bolts**

The following problem was suggested by Rawlins in 1992: Suppose you are given a collection of n nuts and n bolts. Each bolt fits exactly one nut, and otherwise, the nuts and bolts have distinct sizes. The sizes are too close to allow direct comparison between pairs of bolts or pairs of nuts. However, you can compare any nut to any bolt by trying to screw them together; in constant time, you will discover whether the bolt is too large, too small, or just right for the nut. Your task is to discover which bolt fits each nut, or equivalently, to sort the nuts and bolts by size.

A straightforward variant of randomized quicksort solves the problem in $O(n \log n)$ time with high probability. Pick a random bolt; use it to partition the nuts; use the matching nut to partition the bolts; and recurse. However, finding a deterministic algorithm that even runs in $o(n^2)$ is nontrivial. Deterministic $O(n\log n)$-time algorithms were finally found in 1995 by Bradford and independently by Komlós, Ma, and Szemerédi. Under the hood, both algorithms use variants of the AKS parallel sorting network, so the hidden constant in the $O(n\log n)$ time bound is quite large; the hidden constant for the randomized algorithm is 4.

* Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar, and Rafail Ostrovsky. Matching nuts and bolts. *Proc. 5th Ann. ACM-SIAM Symp. Discrete Algorithms*, 690–696, 1994.
* Noga Alon, Phillip G. Bradford, and Rudolf Fleischer. Matching nuts and bolts faster. *Inform. Proc. Lett.* 59(3):123–127, 1996.
* Phillip G. Bradford. Matching nuts and bolts optimally. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. <http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025>
* Phillip G. Bradford and Rudolf Fleischer. Matching nuts and bolts faster. *Proc. 6th. Int. Symp. Algorithms Comput.*, 402–408, 1995. Lecture Notes Comput. Sci. 1004.
* János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in $O(n\log n)$ time. *SIAM J. Discrete Math.* 11(3):347–372, 1998.
* Gregory J. E. Rawlins. *Compared To What? : An Introduction to The Analysis of Algorithms*. Computer Science Press/W. H. Freeman, 1992.

> **Comments:**
> **username_14**: This is a beautiful example, but it's an oracle problem. Is there some way to remove the oracle from it?  
> **username_15**: Got a link to the 98 Szemeredi paper? How is this hard? In parallel compare each bolt to a unique nut and put each pair in sorted order; removing matched elements.  In log(n) steps merge the sorted nbnbnbnbnb sequences, kicking out matches as they arise.  EDIT: Yeah the noncomparability of nnn and bbbb strings is annoying on the merge step.  
> **username_6**: @ChadBrewbaker  Suppose in every pair but one, the bolt is smaller than the nut.  (Yes, this is possible.)  Now what does your algorithm do?  In other words, "annoying" = "the whole problem".  
> **username_15**: I was looking for the Szemeredi paper and thinking out loud how it is hard. Yes, I concur that a merge based approach is nontrivial; but Vishkin's papers on parallel graph connectivity leave a gut feeling it is not impossible.  
> **username_15**: With each comparison from a nut and bolt you get a directed edge added to the graph or a match which removes both vertices. The goal would be to merge connected components in such a way that they collapse all matches between them with a linear amount of work and keep the storage size of edges in a connected component bounded to linear space.  
> **username_6**: In fact, there is a **randomized** mergesort solution, which I've never seen written down.  Flip 2n coins to split the nuts and bolts into two subsets; recursively sort the subsets as as much as possible; merge the two "sorted" lists.  The merge step only needs $O(n)$ expected time, because the expected length of any string of incomparable nuts or bolts is constant (even deep in the recursion).  With high probability, the recursion ends after $O(\log n)$ levels.  

---

### Answer by username_8 on 2012-11-20. Score: 20

Once you are not just talking about poly-time but rather look at the many models of computation we study, there are examples everywhere:

In Logspace: Un-directed ST connectivity (in RL since 1979, and in L only since 2005)

In NC: Finding a perfect matching in a bipartite graph in parallel (in RNC and still not known to be in NC)

In interactive proofs: deterministic ones give NP, while randomized ones can do PSPACE. Related: checking a proof deterministically requires looking at all the proof, while PCP proofs allow you to check only a constant number of bits.

In Algorithmic Mechanism Design: many randomized truthful approximation mechanisms with no deterministic counterpart.

In Communication complexity: the equality function requires linear communication deterministically but logarithmic (or, depending on exact model, constant) communication randomly.

In decision trees: evaluating an and-or tree requires linear queries deterministically but much less with randomization. This is essentially equivalent to alpha-beta pruning which gives a randomized sub-linear algorithm for game-tree evaluation.

In streaming models, distributed computing models: see previous answers.


---

### Answer by username_5 on 2012-11-20. Score: 12

**Most streaming algorithms**

In the streaming model of computation ([AMS](https://www.tau.ac.il/%7Enogaa/PDFS/amsz4.pdf), [book](http://algo.research.googlepages.com/eight.ps)), an algorithm processes an online sequence of updates and is restricted to keep only sublinear space. At any point in time, the algorithm should be able to answer a query.

For many problems there exist sublinear space randomized streaming algorithms while provably no deterministic algorithm can solve the problem in sublinear space. This is related to gaps between randomized and deterministic communication complexity. A simple example is the *distinct count* problem: at each time step $t$ the algorithm is given an integer $i\_t \in [n]$, and it should be able to approximate $D\_m = |\{i\_t: t = 1\ldots m\}|$, i.e. the number of distinct integers seen up to time step $m$. It's relatively easy to show that any deterministic algorithm achieving constant approximation must use $\Omega(n)$ space (see e.g. [lecture notes](https://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec9/lec9.pdf) by Piotr Indyk). On the other hand the [clever sampling algorithm](http://algo.inria.fr/flajolet/Publications/FlMa85.pdf) of Flajolet and Martin (simple analysis with limited randomness in the AMS paper linked above) achieves constant approximation in $O(\log n)$ bits. The [latest work](https://web.archive.org/web/20110107060020/http://www.almaden.ibm.com/cs/people/dpwoodru/knw11.pdf) on the problem gives an optimal $O(\frac{1}{\epsilon^2} + \log n)$ algorithm that computes an $1\pm \epsilon$ approximation.


---

### Answer by username_9 on 2012-11-21. Score: 9

**Majority problem in a query model.**

**Problem**. We are given a set of $n$ balls colored with two or more colors. The goal is to ﬁnd a ball of the majority color (i.e., a color that occurs more than n/2 times) assuming such a color exists, using queries of the form "Does ball $i$ and ball $j$ have the same color?". The strategy must be oblivious, i.e., queries cannot depend on the results of previous queries.

**Randomized Algorithm**. Pick a random ball and check if more than $n/2$ balls have the same color. This algorithm runs in $O(n)$ time in expectation.

**Deterministic $O(n)$ algorithm** is quite non-trivial and is a nice application of expanders.

F. R. K. Chung, R. L. Graham, J. Mao, and A. C. Yao, Oblivious and adaptive strategies for the Majority and Plurality problems, *Proc. COCOON 2005*, pp. 329–338.


---

### Answer by username_10 on 2012-11-20. Score: 9

Finding a **maximal independent set in a distributed network** of $n$ nodes with maximum degree $\Delta$. There's a known lower bound [3] of $\min(\Omega(\log\Delta),\Omega(\sqrt{\log n}))$ that holds for randomized and deterministic algorithms.

The following is a simple randomized distributed algorithm [1] that proceeds in synchronous *rounds*. (In a round, every node $u$ can perform some local computation and send messages to its neighbors. These messages are guaranteed to be received before the start of the next round.)

1. In every round, each active node $u$ marks itself with probability $1/d\_u$ where $d\_u>0$ is the degree of $u$; if $d\_u=0$, $u$ simply enters the independent set. (Initially, every node is active.)
2. If $u$ is the only marked node in its neighborhood, $u$ enters the independent set, deactivates itself and notifies all of its neighbors to deactivate themselves. The degrees of the remaining active nodes are decreased accordingly, i.e., all edges to deactivated nodes are removed.
3. Otherwise, if there is some neighboring node $v$ that is also marked, the lower degree vertex unmarks itself and remains active.

It can be shown that this algorithm terminates in $O(\log n)$ rounds with high probability, by arguing that half of the remaining edges are deleted in every round. In contrast, the fastest known deterministic distributed algorithm [2] takes $O(n^{1/\sqrt{\log n}})$ rounds and is considerably more complicated.

---

[1] Michael Luby: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15(4): 1036-1053 (1986)
<http://dx.doi.org/10.1137/0215074>

[2] Alessandro Panconesi, Aravind Srinivasan: On the Complexity of Distributed Network Decomposition. J. Algorithms 20(2): 356-374 (1996)
<http://dx.doi.org/10.1006/jagm.1996.0017>

[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
<http://arxiv.org/abs/1011.5470>

> **Comments:**
> **username_11**: A recent algorithm (at PODC 2013), inspired by biological systems, achieves performance as good as Luby's by using a simple local feedback mechanism.  http://arxiv.org/abs/1211.0235  

---

### Answer by username_10 on 2012-11-20. Score: 7

## Leader Election in an Anonymous Ring of Processes

Suppose that you have a ring network of processes that do not have ids and that communicate by message passing. Initially, every process is in the same state.
You want to design a distributed algorithm such that eventually exactly $1$ process enters the *elected* state and all other processes enter the *non-elected* state. This is the so called leader election problem which is one of the fundamental symmetry breaking tasks in a distributed system and has many applications.

There's a simple argument (e.g. [1]) that there is no *deterministic* leader election algorithm for an anonymous ring.

**Model:** We assume that the computation advances in synchronous rounds where, in each round, every process performs some local computation, sends messages to its neighbors in the ring, and receives messages from its neighbors.

For the sake of a contradiction, let's assume that there is such a deterministic leader election algorithm $A$.
It is sufficient to show that, at the start of any round $r\ge 0$, all processes are in the same state, since this implies that there cannot be exactly $1$ process in the *elected* state.
Since processes do not have ids and the network is symmetric, every process is in the same initial state, which provides the induction base.

For the induction step, consider some round $r\ge 0$ and assume that every process is in the same state at the start of round $r$. Therefore, since algorithm $A$ is deterministic, every process performs exactly the same computation and sends exactly the same messages during round $r$. This in turn implies that every process receives exactly the same messages during $r$ and, by the start of round $r+1$, is in the same state. Thus, no such algorithm $A$ can exist.

If $A$ is a randomized algorithm on the other hand and processes know the size of the ring $n$, there's an easy way to break symmetry, by generating a random id from the range $[1,n^4]$, which will result in unique ids for all processes with high probability. A simple and naive algorithm proceeds by letting every process send its id along the ring and instruct processes to forward only messages containing the largest id seen so far. This guarantees that only the process who generated the largest id will receive its own message once it has traversed the entire ring and elect itself as the leader.

---

[1] Dana Angluin: Local and Global Properties in Networks of Processors (Extended Abstract). STOC 1980: 82-93.
<http://doi.acm.org/10.1145/800141.804655>


---

### Answer by username_12 on 2022-08-16. Score: 4

Finding square roots modulo prime number:

<https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm>


---

### Answer by username_2 on 2022-07-16. Score: 2

Finding a 2-approximate weighted vertex cover is known to be in RNC [1]. I don't think it is known to be in NC. That is, the problem has a randomized poly-log-time poly-processor algorithm, but I don't think it is known to have a deterministic poly-log-time poly-processor algorithm.

[1] <https://dx.doi.org/10.1007/s00446-011-0127-7>


---

### Answer by username_13 on 2022-08-18. Score: 1

This problem defined in 1982 by Papadimitriou and Yannakakis:

Exact Perfect Matching problem

Input: A graph G, with each edge colored red or blue, and integer k.

Problem: Decide whether there exists a perfect matching M in G with exactly k red edges

Exact Perfect Matching lies in the complexity class $RP$ since it has a randomized polynomial time algorithm (given by Mulmuley, Vazirani and Vazirani ). Therefor it is unlikely to be $NP$-hard.


---

