39
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ Closely related: Problems in BPP not known to be in P $\endgroup$ – usul Apr 19 '15 at 23:56
  • $\begingroup$ 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.) $\endgroup$ – D.W. Apr 20 '15 at 22:38
  • 1
    $\begingroup$ 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! $\endgroup$ – Dana Moshkovitz Apr 21 '15 at 13:22
  • $\begingroup$ 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. $\endgroup$ – usul Apr 21 '15 at 22:23
  • $\begingroup$ @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. $\endgroup$ – D.W. Apr 22 '15 at 21:27
28
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 20 '15 at 9:18
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 20 '15 at 9:24
19
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeremy Kun Apr 20 '15 at 3:11
9
$\begingroup$

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).
$\endgroup$
1
$\begingroup$

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

$\endgroup$
-5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm new to cstheory.SE. So, downvoters -- what's wrong with this answer? $\endgroup$ – galdre Apr 21 '15 at 1:50
  • 3
    $\begingroup$ 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.) $\endgroup$ – Yuval Filmus Apr 21 '15 at 5:40
  • 2
    $\begingroup$ cstheory.se is about theoretical computer science*, not the practice of programming. Like it or not, the two areas are quite separate. $\endgroup$ – Yuval Filmus Apr 21 '15 at 5:41
  • 2
    $\begingroup$ @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. $\endgroup$ – William Hird Apr 21 '15 at 23:31
  • 2
    $\begingroup$ @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 . $\endgroup$ – Emil Jeřábek Apr 22 '15 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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