[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Derandomization is the process of taking a randomized algorithm and turning it into a deterministic algorithm. This is useful both for practical reasons (deterministic algorithms are more predictable, which makes them easier to debug and gives hard guarantees on running time) and theoretical reasons (if we can derandomize any randomized algorithm we could show results like P=RP, which would reduce the number of complexity classes that complexity theorists otherwise have to deal with).

1. Adleman's theorem

Short version: RP ⊆ P/poly. This means that given a machine M(x,r) that outputs 1 at least half the time when x∈L and never when x∉L, there is a polynomial-sized string of advice pn that depends only on the size of the input n and a machine M' such that M'(x,p|x|) outputs 1 if and only if x∈L.

Proof: We'll use the union bound (see ProbabilisticInequalities). Consider any fixed input x of size n, and imagine running M repeatedly on this input with n+1 independent sequences of random bits r1, r2 ..., rn+1. If x∉L, then M(x,ri) never outputs 1. If x∈L, then for each ri there is an independent probability of at least 1/2 that M(x,ri) = 1. So Pr[M(x,ri) = 0] ≤ 1/2, and Pr[∀i M(x,ri) = 0] ≤ 2^-(n+1)^. If we sum this probability of failure for each individual x∈L over the at most 2^n^ elements of L, we get a probability that any of them fail of at most 2^n^2^-(n+1)^ = 1/2. Turning this upside down, any sequence of n+1 random inputs includes a '''witness''' that x∈L for ''all'' inputs x with probability at least 1/2. It follows that a good sequence r1...rn,, exists.

Our advice pn is now some good sequence <r1...rn+1>, and the deterministic advice-taking algorithm that uses it is:

M'(x,<r,,1,,...r,,n+1,,>):
  for i = 1..n+1:
    if M(x,r,,i,,) = 1:
      return 1
  return 0

The classic version of this theorem shows that anything you can do with a polynomial-size randomized circuit (a circuit made up of AND, OR, and NOT gates where some of the inputs are random bits, corresponding to the r input to M) can be done with a polynomial-size deterministic circuit (where now the pn input is baked into the circuit, since we need a different circuit for each size n anyway). This shows that ordinary algorithms are better described by uniform families of circuits, where there exists a polynomial-time algorithm that, given input n, outputs the circuit Cn for processing size-n inputs. The class of circuits generated by Adleman's theorem is most likely non-uniform: the process of finding the good witnesses ri (especially the later ones) is not something we can clearly do in polynomial time (with the usual caveat that we can't prove much about what we can't do in polynomial time).


CategoryRandomizedAlgorithmsNotes


2014-06-17 11:58