<p>I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best known deterministic algorithms are $\tilde O(n^4)$ assuming GRH (deterministic Miller–Rabin) or $\tilde O(n^6)$ unconditionally (variants of AKS).</p>

CC BY-SA 3.0
2015-04-20T09:18:07.660Z
Though there are reasons to believe that the smallest compositeness witness for $N$ is of the order $\log N\log\log N$, which would give an $\tilde O(n^3)$ algorithm. But this remains unproven even under standard number-theoretic conjectures like variants of RH.
Emil Jeřábek
CC BY-SA 3.0
2015-04-20T09:24:19.273Z
A problem in a similar vein is polynomial irreducibility testing over finite fields, where again known deterministic algorithm have worse bounds than randomized algorithms, but I do not remember the details.
Emil Jeřábek
CC BY-SA 3.0
2015-04-19T21:16:46.697Z
2015-04-20T09:06:16.360Z
2015-04-20T09:06:16.360Z
Emil Jeřábek
<p>An old example is volume computation. Given a polytope described by a membership oracle, there's a randomized algorithm running in polynomial time to estimate its volume to a $1+\epsilon$ factor, but no deterministic algorithm can come even close <strong>unconditionally</strong>.</p>

<p>The first example of such a randomized strategy was by Dyer, Frieze and Kannan, and the hardness result for deterministic algorithms is by Bárány and Füredi. Alistair Sinclair <a href="http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf">has nice lecture notes on this</a>. </p>

<p>I'm not sure I fully understand the "and it shouldn't" part of the question, so I'm not sure this fits the bill. </p>

CC BY-SA 3.0
2015-04-20T03:11:03.167Z
I was aware of the MCMC method but not this lower bound, and I am quite surprised (I thought all that was known was #P-hardness). The paper is "Computing the Volume is Difficult," accessible from [Füredi's webpage](http://www.math.uiuc.edu/~z-furedi/PUBS/), and they give a lower bound of essentially $[n / \log n]^n$ on how well the volume can be approximated.
Jeremy Kun
CC BY-SA 4.0
2020-01-20T10:18:03.683Z
Is it correcting that *constructing* an adversarial convex body is intractable if P = BPP?
Geoffrey Irving
CC BY-SA 3.0
2015-04-20T02:50:43.000Z
2015-04-20T02:50:43.000Z
Suresh Venkat
<p>i dont know if this answers your question (or at least part of it). But for real-world examples where randomisation can provide a speed-up is in optimisation problems and the relation to the <a href="http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization" rel="noreferrer">No Free Lunch (<strong>NFL</strong>) theorem</a>.</p>
<p>There is a paper <a href="http://www.martinsewell.com/evolutionary-computation/nfl/DrJW98.pdf" rel="noreferrer">&quot;Perhaps not a free lunch but at least a free appetizer&quot;</a> where it is shown that employing randomisation, (optimisation) algorithms can have better performance.</p>
<blockquote>
<p><strong>Abstract:</strong></p>
<p>It is often claimed that Evolutionary Algorithms are superior to other optimization techniques, in particular, in situations where not much is known about the objective function to be optimized.  In contrast to that Wolpert and Macready (1997) proved that all optimization techniques have the same behavior --- on average over all <span class="math-container">$f : X \rightarrow Y$</span> where <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are finite sets.  This result is called [the] No Free Lunch Theorem.  Here different scenarios of optimization are presented.  It is argued why the scenario on which the No Free Lunch Theorem is based does not model real life optimization.  For more realistic scenarios it is argued why optimization techniques differ in their efficiency.  For a small example this claim is proved.</p>
</blockquote>
<p>References:</p>
<ol>
<li><a href="http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf" rel="noreferrer">No Free Lunch Theorems for Optimization</a> (original <strong>NFL</strong> theorem for optimisation)</li>
<li><a href="http://www.martinsewell.com/evolutionary-computation/nfl/DrJW98.pdf" rel="noreferrer">Perhaps not a free lunch but at least a free appetizer</a></li>
<li><a href="http://www.cs.colostate.edu/%7Egenitor/2001/gecco2001.pdf" rel="noreferrer">The No Free Lunch and description length</a> (shows that <strong>NFL</strong> results hold for any subset <span class="math-container">$F$</span> of the set of all possible functions iff <span class="math-container">$F$</span> is closed under permutation, <strong>c.u.p.</strong>)</li>
<li><a href="http://image.diku.dk/igel/paper/OCoFfwNFLRH.pdf" rel="noreferrer">On classes of functions for which No Free Lunch results hold</a> (It is proven that the fraction of subsets that are <strong>c.u.p.</strong> is negligibly small)</li>
<li><a href="http://www.cs.cmu.edu/%7Ematts/Research/mstreeter_gecco_2003.pdf" rel="noreferrer">Two Broad Classes of Functions for which a No Free Lunch Result Does Not Hold</a> (shows that a <strong>NFL</strong> result does not apply to a set of functions when the description length of the functions is sufficiently bounded)</li>
<li><a href="https://hal.inria.fr/inria-00369788/document" rel="noreferrer">Continuous lunches are free plus the design of optimal optimization algorithms</a> (shows that for continuous domains, [official version of] <strong>NFL</strong> does not hold. This free-lunch theorem is based on the formalization of the concept of random fitness functions by means of random fields)</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.172.6290&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Beyond No Free Lunch: Realistic Algorithms for Arbitrary Problem Classes</a> (shows that &quot;..[a]ll violations of the No Free Lunch  theorems  can  be  expressed  as  non-block-uniform distributions  over  problem  subsets  that  are <strong>c.u.p.</strong>&quot;)</li>
<li><a href="http://cdn.intechopen.com/pdfs/32858.pdf" rel="noreferrer">Swarm-Based Metaheuristic Algorithms and No-Free-Lunch Theorems</a> (&quot;[..t]herefore, results for non-revisiting time-ordered iterations may not be true for the cases of revisiting cases, because the revisiting iterations break an important assumption of <strong>c.u.p.</strong> required for proving the NFL theorems (Marshall and Hinton, 2010)&quot;)</li>
<li><a href="http://www.cs.bham.ac.uk/%7Ewbl/biblio/gecco2006etc/papers/lbp124.pdf" rel="noreferrer">No Free Lunch and Algorithmic Randomness</a></li>
<li><a href="http://duenez.evolicious.org/PDFs/Duenez2012a.pdf" rel="noreferrer">No Free Lunch and Benchmarks</a> (a set-theoretic approach it is generalised to criteria not-specific to <strong>c.u.p.</strong>, but still notes that (non-trivial) randomised algorithms can outperform deterministic algorithms on average, &quot;[..]it has been demonstrated that probability is inadequate to affirm unconstrained <strong>NFL</strong> results in the general case. [..]this paper abandons probability, preferring a set-theoretic framework which obviates measure-theoretic limitations by dispensing with probability altogether&quot;)</li>
</ol>
<p>Summary on no-free-lunches (and free lunches) by David H. Wolpert, <a href="http://www.no-free-lunch.org/coev.pdf" rel="noreferrer">What does dinner cost?</a> (<strong>note</strong> that <em>NFL-type</em> theorems never specify an actual &quot;<em>price</em>&quot; due to their type of proof)</p>
<p>specificaly for generalised optimisation (GO):</p>
<blockquote>
<ol>
<li><p>Two spaces <span class="math-container">$X$</span> and <span class="math-container">$Z$</span>. E.g., <span class="math-container">$X$</span> is inputs, <span class="math-container">$Z$</span> is distributions over outputs.</p>
</li>
<li><p>Fitness Function <span class="math-container">$f:  X \to Z$</span></p>
</li>
<li><p><span class="math-container">$m$</span> (perhaps repeated) sampled points of <span class="math-container">$f$</span>: <span class="math-container">$$d_m =  \{d_m(1), d_m(2), ..., d_m(m)\}$$</span> where <span class="math-container">$\forall t$</span>,
<span class="math-container">$$d_m(t) =\{d^X_m(t),d^Z_m(t)\}$$</span>
each <span class="math-container">$d^Z_m(t)$</span> a (perhaps stochastic) function of <span class="math-container">$f[d^X_m(t)]$</span></p>
</li>
<li><p>Search algorithm <span class="math-container">$a  = \{d_t \to d^X_m(t) : t=0..m\}$</span></p>
</li>
<li><p>Euclidean vector-valued Cost function <span class="math-container">$C(f, d_m)$</span></p>
</li>
<li><p>To capture a particular type of optimization problem,much of the problem structure is expressed in <span class="math-container">$C(., .)$</span></p>
</li>
</ol>
<p><strong>NFL theorems depend crucially on having <span class="math-container">$C$</span> be independent of <span class="math-container">$f$</span>. If <span class="math-container">$C$</span> depends on <span class="math-container">$f$</span>, free lunches may be possible. E.g., have <span class="math-container">$C$</span>
independent of <span class="math-container">$(f, d_m)$</span>, unless <span class="math-container">$f = f^*$</span>.</strong></p>
</blockquote>
<p>Finally a simple (and a not-so-simple) remark why <strong>randomisation</strong> (in one form or another) may provide superior performance over strictly deterministic algorithms.</p>
<ol>
<li>In the context of <em>optimisation</em> (although not restricted in this), a randomised search procedure can <strong>on the average</strong> <em>escape</em> local-extrema better than deterministic search, and reach global-extrema.</li>
<li>There is an interesting (but also not simple at a first glance) relation between ordering, cardinality and randomisation of a set (in the general sense). The powerset <span class="math-container">$2^A$</span> of a set <span class="math-container">$A$</span> (and its cardinality), intrinsicaly depends on a certain (staticaly) fixed ordering of the set (elements of) <span class="math-container">$A$</span>. Assuming the ordering on (elements of) <span class="math-container">$A$</span> is not (staticaly) fixed (randomisation can enter here, in the form of random ordering), the set <span class="math-container">$A$</span> may be able to represent its own powerset (if it helps think of it as a kind of <em>quantum analog</em> of a classic set, where dynamic ordering plays such a role as to account for a kind of <em>superposition principle</em>).</li>
</ol>

CC BY-SA 3.0
2015-04-21T05:50:13.770Z
2015-12-31T21:34:20.420Z
2020-06-17T09:38:08.363Z
Nikos M.
<p>Grigoriadis and Khachiyan's paper <a href="https://scholar.google.com/scholar?cluster=3647150107566098261&amp;hl=en&amp;as_sdt=0,22" rel="nofollow noreferrer">A sublinear-time randomized approximation algorithm for matrix games</a> gives a sublinear-time randomized algorithm for computing an additive <span class="math-container">$\epsilon$</span>-approximate solution to any zero-sum game with payoffs in <span class="math-container">$[0,1]$</span> (with high probability).  If I recall correctly it's not hard to show by an adversary argument that there is provably no sublinear-time deterministic algorithm that does the same.  </p>

<p>Not sure if you would say in this case that randomization <em>shouldn't</em> help.  Informally, it feels a bit like random sampling, and it seems to me natural to say that randomization <em>should</em> help random sampling.</p>

CC BY-SA 4.0
2020-01-20T01:55:45.603Z
2020-01-20T01:55:45.603Z
Neal Young
<p>Best example is in area considered currently best candidates for OWFs where it seems every popular OWF that is cooked up surprisingly has a randomized sub-exponential algorithm while there exists no deterministic sub-exponential algorithm (take integer factorization for instance). In fact, in many cases, there probably is efficient algorithm given some advice strings (cryptoanalysis).</p>

CC BY-SA 3.0
2015-04-19T20:26:49.303Z
2015-04-19T20:44:25.430Z
2015-04-19T20:44:25.430Z
Turbo
<p>A number of people have commented that there is no difference between random and pseudorandom, and that any random function can be emulated deterministically. This is not true.</p>

<p>Imagine you have two dice.</p>

<ul>
<li>One has 3 sides and an unkown bias</li>
<li><p>The other has 12 sides and no bias</p></li>
<li><p><code>S</code> is the number on the 3 sided die after rolling it</p></li>
<li><code>N</code> is the number on the 12 sided die after rolling it</li>
<li><code>I</code> is <code>S</code> hashed <code>N</code> times</li>
</ul>

<p>Your function input is <code>I</code> and you are to determine <code>S</code>. You do so by choosing a possible value for <code>S</code> and trying to hash it up to 12 times, stopping when you reach <code>I</code>.</p>

<p>If your function is deterministic you start with an arbitrary <code>S</code> or your choose an arbitrary <code>S</code> based on <code>I</code>. If you are lucky, the 3 sided dice will be biased towards your arbitrarilly chosen <code>S</code>, but there is a 2/3rds chance that your arbitrarilly chosen starting <code>S</code> will be a worse than random starting point. Even if you are able to make a pseudorandom choice of a starting <code>S</code> based on <code>I</code>, you will still have a bias, and you are more likely than not, that this bias will be non-concordant with the unknown bias of the 3 sided dice.</p>

CC BY-SA 4.0
2020-01-24T15:13:58.777Z
2020-01-24T15:13:58.777Z
timthelion
<p>If you have an algorithm using randomisation, you can always replace it with a deterministic algorithm using pseudo-random numbers: Take the description of the problem, calculate a hash code, use that hash code as the seed for a good pseudo-random number generator. In practice, that's actually what is likely to happen when somebody implements an algorithm using randomisation. </p>

<p>If we leave out the hash code, then the difference between this algorithm and an algorithm using true randomisation is that I can predict the sequence of random numbers generated, and I could produce a problem such that the predicted random number applied to my problem will always make the worst possible decision. For example, for Quicksort with a pseudo-random pivot I could construct an input array where the pseudo-random pivot  will always find the largest possible value in the array. With true randomness that isn't possible. </p>

<p>With the hash code, it would be <em>very difficult</em> for me to construct a problem where the pseudo-random numbers produce worst outcomes. I can still predict the random numbers, but if I change the problem, the sequence of pseudo-random numbers changes completely. Still, it would be close to impossible for you to <em>prove</em> that I can't construct such a problem. </p>

CC BY-SA 3.0
2015-04-21T01:50:53.020Z
I'm new to cstheory.SE. So, downvoters -- what's wrong with this answer?
galdre
CC BY-SA 3.0
2015-04-21T05:40:52.493Z
Two things are wrong: (1) we don't know how to construct pseudorandom numbers in general, (2) even when we do know how to construct them, they are computationally expensive. Pseudorandom numbers used in practice are not guaranteed to work in theory; all we know is that they seem to work empirically. (Indeed, most of the PRNGs actually in use can be broken, so they are actually not safe for use in general, only when you're not specifically trying to break them.)
Yuval Filmus
CC BY-SA 3.0
2015-04-21T05:41:53.503Z
cstheory.se is about *theoretical* computer science*, not the practice of programming. Like it or not, the two areas are quite separate.
Yuval Filmus
CC BY-SA 3.0
2015-04-21T23:31:48.423Z
@YuvalFilmus: The Alternating Step Generator invented by C. Gunther back in 1987 has not been broken yet ( no public break yet, and I doubt the NSA has broken it either). Twenty-eight years is a long time to remain unbroken, I am amazed that such a simple generator ( three LFSR's and one XOR gate,how simple is that?) has not been broken yet and is not used more often.
William Hird
CC BY-SA 3.0
2015-04-22T09:09:05.083Z
@WilliamHird: Depending on a definition of "broken", it seems to have been actually broken (more or less to a similar extent as the related, more efficient, and widely used A5/x family). See  http://crypto.stackexchange.com/a/342 .
Emil Jeřábek
CC BY-SA 3.0
2015-04-22T16:35:31.537Z
@EmilJeřábek: Broken means a polynomial time algorithm for finding the secret key(s). The A5 family is a weakened version of Gunther's design. If you just stick with Gunther's version and the key lengths for all three shift registers are at least 128 bits, there is no public break for the generator in P. If there is , send me a link to THAT paper!
William Hird
CC BY-SA 3.0
2015-04-22T18:02:47.987Z
Polynomial time is not a reasonable option, as then essentially none of these symmetric ciphers/PRG are “broken”. A reasonable definition for purposes of derandomization of BPP would be subexponential time, and for practical cryptographic purposes $2^{\epsilon n}$ with $\epsilon<1$. Also, A5 is not a weakened version of ASC. If anything, it is substantially *stronger*, in that it needs roughly 3 times shorter total key length to achieve the same level of security. In any case, this is getting off topic.
Emil Jeřábek
CC BY-SA 3.0
2015-04-22T19:21:02.317Z
@EmilJeřábek: You and I must have gradu-mutated from different cryptography schools! A5 was easily broken because its key lengths were too small! That means it is a weaker cipher than one with a larger key. You are confusing strength with efficiency. But you are right , we are getting away from topic. Finis.
William Hird
CC BY-SA 3.0
2015-04-20T09:42:28.613Z
2015-04-20T09:42:28.613Z
gnasher729
<p>Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic algorithm for the problem that runs in time $\Theta(t(n)\cdot n)$ on inputs of size $n$ [the algorithm runs the randomized algorithm on $\Theta(n)$ independent randomness strings. There must be randomness for the repeated algorithm that is good for all $2^n$ possible inputs]. The deterministic algorithm is non-uniform - it may behave differently for different input sizes.
So Adleman's argument shows that - if one doesn't care about uniformity - randomization can only speed-up algorithms by a factor that is linear in the input size.</p>

<p>What are some concrete examples where randomization speeds up computation (to the best of our knowledge)?</p>

<p>One example is polynomial identity testing. Here the input is an n-sized arithmetic circuit computing an m-variate polynomial over a field, and the task is to find out whether the polynomial is identically zero. A randomized algorithm can evaluate the polynomial on a random point, while the best deterministic algorithm we know (and possibly the best that exists) evaluates the polynomial on many points. </p>

<p>Another example is minimum spanning tree, where the best randomized algorithm by Karger-Klein-Tarjan is linear time (and the error probability is exponentially small!), while the best deterministic algorithm by Chazelle runs in time $O(m\alpha(m,n))$ ($\alpha$ is the inverse Ackermann function, so the randomization speed-up is really small). Interestingly, it was proved by Pettie and Ramachandran that if there's a non-uniform deterministic linear time algorithm for minimum spanning tree, then there also exists a uniform deterministic linear time algorithm.</p>

<p>What are some other examples?
Which examples do you know where the randomization speed-up is large, but this is possibly just because we haven't found sufficiently efficient deterministic algorithms yet?  </p>

CC BY-SA 3.0
2015-04-19T23:56:37.720Z
Closely related: [Problems in BPP not known to be in P](http://cstheory.stackexchange.com/questions/27974/problems-in-mathsfbpp-not-known-to-be-in-mathsf-p)
usul
CC BY-SA 3.0
2015-04-20T22:38:10.673Z
You can always convert any randomized algorithm into a deterministic algorithm, by replacing the random generator with a cryptographic-quality pseudorandom generator.  Under plausible cryptographic assumptions that to the best of our knowledge are valid, this works fine.  Therefore, my answer would be: "to the best of our knowledge, the answer is: there aren't any such real-world problems".  (In other words, to the best of our knowledge, the gap in runtime reflects our inability to prove tight runtime bounds rather than any real underlying difference.)
D.W.
CC BY-SA 3.0
2015-04-21T13:22:38.143Z
Under reasonable hardness assumptions you can feed the algorithm randomness from a pseudorandom generator, however to actually get a deterministic algorithm out of that, you need to run the algorithm on all possible seeds. This blows-up the run-time!
Dana Moshkovitz
CC BY-SA 3.0
2015-04-21T22:23:58.627Z
In addition to Dana's point, I think that to derandomize BPP, the PRG needs to run in more time than the original algorithm (though I don't know what the gap has to be). Also, this might illustrate a (fundamental?) gap between certainty and exponentially-high confidence: It suffices to repeat a randomized algorithm $c$ times (for any constant $c$) to get correctness probability $2^{-O(c)}$, but the deterministic version needs to check all polynomially many seeds.
usul
CC BY-SA 3.0
2015-04-22T21:27:04.123Z
@DanaMoshkovitz, it depends whether you approach this from a theoretical perspective or a practitioner perspective. From a practitioner perspective, no, you don't need to do that. See the construction I outline in http://cs.stackexchange.com/a/41723/755, which runs the algorithm on just $O(1)$ seeds. Under the random oracle model one can show that there is no increase in asymptotic runtime and no computationally-bounded adversary is likely to be able to find any input to the algorithm where the algorithm produces the wrong answer. This is probably good enough for all practical purposes.
D.W.
CC BY-SA 3.0
2015-12-21T16:46:45.987Z
To clarify, since I found the statement about MST very surprising: what [Pettie and Ramachandran](http://dx.doi.org/10.1145/505241.505243) show is that the uniform runtime for MST is no more than a constant multiple of its decision-tree complexity. As far as I can tell, they do *not* show that $MST \in \mathsf{TIME}(O(n))\mathsf{/lin}$ implies $MST \in \mathsf{TIME}(O(n))$ (which is the statement that initially surprised me).
Joshua Grochow
CC BY-SA 3.0
2015-12-24T01:43:30.623Z
Even more closely related: [Does randomness buy us anything inside P?](http://cstheory.stackexchange.com/questions/11738/does-randomness-buy-us-anything-inside-p/14454#14454)  Also [Efficient and simple randomized algorithms where determinism is difficult](http://cstheory.stackexchange.com/questions/14396/efficient-and-simple-randomized-algorithms-where-determinism-is-difficult).
Neal Young
<randomized-algorithms>
When does randomization speed up algorithms and it "shouldn't"?
Dana Moshkovitz
# When does randomization speed up algorithms and it "shouldn't"?

(Asked by: username_0 on 2015-04-19)

Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic algorithm for the problem that runs in time $\Theta(t(n)\cdot n)$ on inputs of size $n$ [the algorithm runs the randomized algorithm on $\Theta(n)$ independent randomness strings. There must be randomness for the repeated algorithm that is good for all $2^n$ possible inputs]. The deterministic algorithm is non-uniform - it may behave differently for different input sizes.
So Adleman's argument shows that - if one doesn't care about uniformity - randomization can only speed-up algorithms by a factor that is linear in the input size.

What are some concrete examples where randomization speeds up computation (to the best of our knowledge)?

One example is polynomial identity testing. Here the input is an n-sized arithmetic circuit computing an m-variate polynomial over a field, and the task is to find out whether the polynomial is identically zero. A randomized algorithm can evaluate the polynomial on a random point, while the best deterministic algorithm we know (and possibly the best that exists) evaluates the polynomial on many points.

Another example is minimum spanning tree, where the best randomized algorithm by Karger-Klein-Tarjan is linear time (and the error probability is exponentially small!), while the best deterministic algorithm by Chazelle runs in time $O(m\alpha(m,n))$ ($\alpha$ is the inverse Ackermann function, so the randomization speed-up is really small). Interestingly, it was proved by Pettie and Ramachandran that if there's a non-uniform deterministic linear time algorithm for minimum spanning tree, then there also exists a uniform deterministic linear time algorithm.

What are some other examples?
Which examples do you know where the randomization speed-up is large, but this is possibly just because we haven't found sufficiently efficient deterministic algorithms yet?

**Tags:** randomized-algorithms
> **Comments:**
> **username_1**: Closely related: [Problems in BPP not known to be in P](http://cstheory.stackexchange.com/questions/27974/problems-in-mathsfbpp-not-known-to-be-in-mathsf-p)  
> **username_2**: You can always convert any randomized algorithm into a deterministic algorithm, by replacing the random generator with a cryptographic-quality pseudorandom generator.  Under plausible cryptographic assumptions that to the best of our knowledge are valid, this works fine.  Therefore, my answer would be: "to the best of our knowledge, the answer is: there aren't any such real-world problems".  (In other words, to the best of our knowledge, the gap in runtime reflects our inability to prove tight runtime bounds rather than any real underlying difference.)  
> **username_0**: Under reasonable hardness assumptions you can feed the algorithm randomness from a pseudorandom generator, however to actually get a deterministic algorithm out of that, you need to run the algorithm on all possible seeds. This blows-up the run-time!  
> **username_1**: In addition to Dana's point, I think that to derandomize BPP, the PRG needs to run in more time than the original algorithm (though I don't know what the gap has to be). Also, this might illustrate a (fundamental?) gap between certainty and exponentially-high confidence: It suffices to repeat a randomized algorithm $c$ times (for any constant $c$) to get correctness probability $2^{-O(c)}$, but the deterministic version needs to check all polynomially many seeds.  
> **username_2**: @DanaMoshkovitz, it depends whether you approach this from a theoretical perspective or a practitioner perspective. From a practitioner perspective, no, you don't need to do that. See the construction I outline in http://cs.stackexchange.com/a/41723/755, which runs the algorithm on just $O(1)$ seeds. Under the random oracle model one can show that there is no increase in asymptotic runtime and no computationally-bounded adversary is likely to be able to find any input to the algorithm where the algorithm produces the wrong answer. This is probably good enough for all practical purposes.  
> **username_3**: To clarify, since I found the statement about MST very surprising: what [Pettie and Ramachandran](http://dx.doi.org/10.1145/505241.505243) show is that the uniform runtime for MST is no more than a constant multiple of its decision-tree complexity. As far as I can tell, they do *not* show that $MST \in \mathsf{TIME}(O(n))\mathsf{/lin}$ implies $MST \in \mathsf{TIME}(O(n))$ (which is the statement that initially surprised me).  
> **username_4**: Even more closely related: [Does randomness buy us anything inside P?](http://cstheory.stackexchange.com/questions/11738/does-randomness-buy-us-anything-inside-p/14454#14454)  Also [Efficient and simple randomized algorithms where determinism is difficult](http://cstheory.stackexchange.com/questions/14396/efficient-and-simple-randomized-algorithms-where-determinism-is-difficult).  

---

## 7 answers

### Answer by username_5 on 2015-04-19. Score: 30

I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best known deterministic algorithms are $\tilde O(n^4)$ assuming GRH (deterministic Miller–Rabin) or $\tilde O(n^6)$ unconditionally (variants of AKS).

> **Comments:**
> **username_5**: Though there are reasons to believe that the smallest compositeness witness for $N$ is of the order $\log N\log\log N$, which would give an $\tilde O(n^3)$ algorithm. But this remains unproven even under standard number-theoretic conjectures like variants of RH.  
> **username_5**: A problem in a similar vein is polynomial irreducibility testing over finite fields, where again known deterministic algorithm have worse bounds than randomized algorithms, but I do not remember the details.  

---

### Answer by username_6 on 2015-04-20. Score: 20

An old example is volume computation. Given a polytope described by a membership oracle, there's a randomized algorithm running in polynomial time to estimate its volume to a $1+\epsilon$ factor, but no deterministic algorithm can come even close **unconditionally**.

The first example of such a randomized strategy was by Dyer, Frieze and Kannan, and the hardness result for deterministic algorithms is by Bárány and Füredi. Alistair Sinclair [has nice lecture notes on this](http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf).

I'm not sure I fully understand the "and it shouldn't" part of the question, so I'm not sure this fits the bill.

> **Comments:**
> **username_7**: I was aware of the MCMC method but not this lower bound, and I am quite surprised (I thought all that was known was #P-hardness). The paper is "Computing the Volume is Difficult," accessible from [Füredi's webpage](http://www.math.uiuc.edu/~z-furedi/PUBS/), and they give a lower bound of essentially $[n / \log n]^n$ on how well the volume can be approximated.  
> **username_8**: Is it correcting that *constructing* an adversarial convex body is intractable if P = BPP?  

---

### Answer by username_9 on 2015-04-21. Score: 11

i dont know if this answers your question (or at least part of it). But for real-world examples where randomisation can provide a speed-up is in optimisation problems and the relation to the [No Free Lunch (**NFL**) theorem](http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization).

There is a paper ["Perhaps not a free lunch but at least a free appetizer"](http://www.martinsewell.com/evolutionary-computation/nfl/DrJW98.pdf) where it is shown that employing randomisation, (optimisation) algorithms can have better performance.

> **Abstract:**
>
> It is often claimed that Evolutionary Algorithms are superior to other optimization techniques, in particular, in situations where not much is known about the objective function to be optimized. In contrast to that Wolpert and Macready (1997) proved that all optimization techniques have the same behavior --- on average over all $f : X \rightarrow Y$ where $X$ and $Y$ are finite sets. This result is called [the] No Free Lunch Theorem. Here different scenarios of optimization are presented. It is argued why the scenario on which the No Free Lunch Theorem is based does not model real life optimization. For more realistic scenarios it is argued why optimization techniques differ in their efficiency. For a small example this claim is proved.

References:

1. [No Free Lunch Theorems for Optimization](http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf) (original **NFL** theorem for optimisation)
2. [Perhaps not a free lunch but at least a free appetizer](http://www.martinsewell.com/evolutionary-computation/nfl/DrJW98.pdf)
3. [The No Free Lunch and description length](http://www.cs.colostate.edu/%7Egenitor/2001/gecco2001.pdf) (shows that **NFL** results hold for any subset $F$ of the set of all possible functions iff $F$ is closed under permutation, **c.u.p.**)
4. [On classes of functions for which No Free Lunch results hold](http://image.diku.dk/igel/paper/OCoFfwNFLRH.pdf) (It is proven that the fraction of subsets that are **c.u.p.** is negligibly small)
5. [Two Broad Classes of Functions for which a No Free Lunch Result Does Not Hold](http://www.cs.cmu.edu/%7Ematts/Research/mstreeter_gecco_2003.pdf) (shows that a **NFL** result does not apply to a set of functions when the description length of the functions is sufficiently bounded)
6. [Continuous lunches are free plus the design of optimal optimization algorithms](https://hal.inria.fr/inria-00369788/document) (shows that for continuous domains, [official version of] **NFL** does not hold. This free-lunch theorem is based on the formalization of the concept of random fitness functions by means of random fields)
7. [Beyond No Free Lunch: Realistic Algorithms for Arbitrary Problem Classes](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.172.6290&rep=rep1&type=pdf) (shows that "..[a]ll violations of the No Free Lunch theorems can be expressed as non-block-uniform distributions over problem subsets that are **c.u.p.**")
8. [Swarm-Based Metaheuristic Algorithms and No-Free-Lunch Theorems](http://cdn.intechopen.com/pdfs/32858.pdf) ("[..t]herefore, results for non-revisiting time-ordered iterations may not be true for the cases of revisiting cases, because the revisiting iterations break an important assumption of **c.u.p.** required for proving the NFL theorems (Marshall and Hinton, 2010)")
9. [No Free Lunch and Algorithmic Randomness](http://www.cs.bham.ac.uk/%7Ewbl/biblio/gecco2006etc/papers/lbp124.pdf)
10. [No Free Lunch and Benchmarks](http://duenez.evolicious.org/PDFs/Duenez2012a.pdf) (a set-theoretic approach it is generalised to criteria not-specific to **c.u.p.**, but still notes that (non-trivial) randomised algorithms can outperform deterministic algorithms on average, "[..]it has been demonstrated that probability is inadequate to affirm unconstrained **NFL** results in the general case. [..]this paper abandons probability, preferring a set-theoretic framework which obviates measure-theoretic limitations by dispensing with probability altogether")

Summary on no-free-lunches (and free lunches) by David H. Wolpert, [What does dinner cost?](http://www.no-free-lunch.org/coev.pdf) (**note** that *NFL-type* theorems never specify an actual "*price*" due to their type of proof)

specificaly for generalised optimisation (GO):

> 1. Two spaces $X$ and $Z$. E.g., $X$ is inputs, $Z$ is distributions over outputs.
> 2. Fitness Function $f: X \to Z$
> 3. $m$ (perhaps repeated) sampled points of $f$: $$d\_m = \{d\_m(1), d\_m(2), ..., d\_m(m)\}$$ where $\forall t$,
>    $$d\_m(t) =\{d^X\_m(t),d^Z\_m(t)\}$$
>    each $d^Z\_m(t)$ a (perhaps stochastic) function of $f[d^X\_m(t)]$
> 4. Search algorithm $a = \{d\_t \to d^X\_m(t) : t=0..m\}$
> 5. Euclidean vector-valued Cost function $C(f, d\_m)$
> 6. To capture a particular type of optimization problem,much of the problem structure is expressed in $C(., .)$
>
> **NFL theorems depend crucially on having $C$ be independent of $f$. If $C$ depends on $f$, free lunches may be possible. E.g., have $C$
> independent of $(f, d\_m)$, unless $f = f^\*$.**

Finally a simple (and a not-so-simple) remark why **randomisation** (in one form or another) may provide superior performance over strictly deterministic algorithms.

1. In the context of *optimisation* (although not restricted in this), a randomised search procedure can **on the average** *escape* local-extrema better than deterministic search, and reach global-extrema.
2. There is an interesting (but also not simple at a first glance) relation between ordering, cardinality and randomisation of a set (in the general sense). The powerset $2^A$ of a set $A$ (and its cardinality), intrinsicaly depends on a certain (staticaly) fixed ordering of the set (elements of) $A$. Assuming the ordering on (elements of) $A$ is not (staticaly) fixed (randomisation can enter here, in the form of random ordering), the set $A$ may be able to represent its own powerset (if it helps think of it as a kind of *quantum analog* of a classic set, where dynamic ordering plays such a role as to account for a kind of *superposition principle*).


---

### Answer by username_4 on 2020-01-20. Score: 2

Grigoriadis and Khachiyan's paper [A sublinear-time randomized approximation algorithm for matrix games](https://scholar.google.com/scholar?cluster=3647150107566098261&hl=en&as_sdt=0,22) gives a sublinear-time randomized algorithm for computing an additive $\epsilon$-approximate solution to any zero-sum game with payoffs in $[0,1]$ (with high probability). If I recall correctly it's not hard to show by an adversary argument that there is provably no sublinear-time deterministic algorithm that does the same.

Not sure if you would say in this case that randomization *shouldn't* help. Informally, it feels a bit like random sampling, and it seems to me natural to say that randomization *should* help random sampling.


---

### Answer by username_10 on 2015-04-19. Score: 1

Best example is in area considered currently best candidates for OWFs where it seems every popular OWF that is cooked up surprisingly has a randomized sub-exponential algorithm while there exists no deterministic sub-exponential algorithm (take integer factorization for instance). In fact, in many cases, there probably is efficient algorithm given some advice strings (cryptoanalysis).


---

### Answer by username_11 on 2020-01-24. Score: 0

A number of people have commented that there is no difference between random and pseudorandom, and that any random function can be emulated deterministically. This is not true.

Imagine you have two dice.

* One has 3 sides and an unkown bias
* The other has 12 sides and no bias
* `S` is the number on the 3 sided die after rolling it
* `N` is the number on the 12 sided die after rolling it
* `I` is `S` hashed `N` times

Your function input is `I` and you are to determine `S`. You do so by choosing a possible value for `S` and trying to hash it up to 12 times, stopping when you reach `I`.

If your function is deterministic you start with an arbitrary `S` or your choose an arbitrary `S` based on `I`. If you are lucky, the 3 sided dice will be biased towards your arbitrarilly chosen `S`, but there is a 2/3rds chance that your arbitrarilly chosen starting `S` will be a worse than random starting point. Even if you are able to make a pseudorandom choice of a starting `S` based on `I`, you will still have a bias, and you are more likely than not, that this bias will be non-concordant with the unknown bias of the 3 sided dice.


---

### Answer by username_12 on 2015-04-20. Score: -5

If you have an algorithm using randomisation, you can always replace it with a deterministic algorithm using pseudo-random numbers: Take the description of the problem, calculate a hash code, use that hash code as the seed for a good pseudo-random number generator. In practice, that's actually what is likely to happen when somebody implements an algorithm using randomisation.

If we leave out the hash code, then the difference between this algorithm and an algorithm using true randomisation is that I can predict the sequence of random numbers generated, and I could produce a problem such that the predicted random number applied to my problem will always make the worst possible decision. For example, for Quicksort with a pseudo-random pivot I could construct an input array where the pseudo-random pivot will always find the largest possible value in the array. With true randomness that isn't possible.

With the hash code, it would be *very difficult* for me to construct a problem where the pseudo-random numbers produce worst outcomes. I can still predict the random numbers, but if I change the problem, the sequence of pseudo-random numbers changes completely. Still, it would be close to impossible for you to *prove* that I can't construct such a problem.

> **Comments:**
> **username_13**: I'm new to cstheory.SE. So, downvoters -- what's wrong with this answer?  
> **username_14**: Two things are wrong: (1) we don't know how to construct pseudorandom numbers in general, (2) even when we do know how to construct them, they are computationally expensive. Pseudorandom numbers used in practice are not guaranteed to work in theory; all we know is that they seem to work empirically. (Indeed, most of the PRNGs actually in use can be broken, so they are actually not safe for use in general, only when you're not specifically trying to break them.)  
> **username_14**: cstheory.se is about *theoretical* computer science*, not the practice of programming. Like it or not, the two areas are quite separate.  
> **username_15**: @YuvalFilmus: The Alternating Step Generator invented by C. Gunther back in 1987 has not been broken yet ( no public break yet, and I doubt the NSA has broken it either). Twenty-eight years is a long time to remain unbroken, I am amazed that such a simple generator ( three LFSR's and one XOR gate,how simple is that?) has not been broken yet and is not used more often.  
> **username_5**: @WilliamHird: Depending on a definition of "broken", it seems to have been actually broken (more or less to a similar extent as the related, more efficient, and widely used A5/x family). See  http://crypto.stackexchange.com/a/342 .  
> **username_15**: @EmilJeřábek: Broken means a polynomial time algorithm for finding the secret key(s). The A5 family is a weakened version of Gunther's design. If you just stick with Gunther's version and the key lengths for all three shift registers are at least 128 bits, there is no public break for the generator in P. If there is , send me a link to THAT paper!  
> **username_5**: Polynomial time is not a reasonable option, as then essentially none of these symmetric ciphers/PRG are “broken”. A reasonable definition for purposes of derandomization of BPP would be subexponential time, and for practical cryptographic purposes $2^{\epsilon n}$ with $\epsilon<1$. Also, A5 is not a weakened version of ASC. If anything, it is substantially *stronger*, in that it needs roughly 3 times shorter total key length to achieve the same level of security. In any case, this is getting off topic.  
> **username_15**: @EmilJeřábek: You and I must have gradu-mutated from different cryptography schools! A5 was easily broken because its key lengths were too small! That means it is a weaker cipher than one with a larger key. You are confusing strength with efficiency. But you are right , we are getting away from topic. Finis.  

---

