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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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 5

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.

Answer 6

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 7

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.