# When does randomization speed up algorithms and it "shouldn't"?

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?

• Closely related: Problems in BPP not known to be in P
– usul
Apr 19, 2015 at 23:56
• 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.
Apr 20, 2015 at 22:38
• 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! Apr 21, 2015 at 13:22
• 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
Apr 21, 2015 at 22:23
• @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 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.
Apr 22, 2015 at 21:27

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

• 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. Apr 20, 2015 at 9:18
• 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. Apr 20, 2015 at 9:24

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.

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.

• 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, and they give a lower bound of essentially $[n / \log n]^n$ on how well the volume can be approximated. Apr 20, 2015 at 3:11
• Is it correcting that constructing an adversarial convex body is intractable if P = BPP? Jan 20, 2020 at 10:18

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.

There is a paper "Perhaps not a free lunch but at least a free appetizer" 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 (original NFL theorem for optimisation)
2. Perhaps not a free lunch but at least a free appetizer
3. The No Free Lunch and description length (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 (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 (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 (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 (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 ("[..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
10. No Free Lunch and Benchmarks (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? (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).

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

Grigoriadis and Khachiyan's paper A sublinear-time randomized approximation algorithm for matrix games 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.

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.

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.

• I'm new to cstheory.SE. So, downvoters -- what's wrong with this answer? Apr 21, 2015 at 1:50
• 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.) Apr 21, 2015 at 5:40
• cstheory.se is about theoretical computer science*, not the practice of programming. Like it or not, the two areas are quite separate. Apr 21, 2015 at 5:41
• @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. Apr 21, 2015 at 23:31
• @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 crypto.stackexchange.com/a/342 . Apr 22, 2015 at 9:09