**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** p_{n} 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 r_{1}, r_{2}_{ ..., r}n+1_{. If x∉L, then M(x,r}i_{) never outputs 1. If x∈L, then for each r}i_{ there is an independent probability of at least 1/2 that M(x,r}i_{) = 1. So Pr[M(x,r}i_{) = 0] ≤ 1/2, and Pr[∀i M(x,r}i_{) = 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 r}1_{...r}n,, exists.

Our advice p_{n} is now some good sequence <r_{1}...r_{n+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 p_{n} 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 C_{n} 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 r_{i} (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).