of counting the number of k-colorings of a given graph, or the number of perfect matchings, etc., whose running time depends on the mixing time (a measure of how fast a random walk “forgets” the starting point) of a Markov chain associated to the algorithm. This approach has led to a rich literature about algorithms that use randomness to efficiently find approximations to several counting problems. Approximations are the best that can be done with efficient algorithms, because exact computations are #P-complete, which is an even stronger evidence of intractability than NP-hardness. Here again we see the phenomenon of a mathematical problem with a determined answer (the value of a high-dimensional integral, or the number of maximal independent sets in a given graph) for which the fastest known way to compute approximations involve the use of randomness.

Given the powerful and indirect ways in which randomness can be used in algorithm design, is it plausible that there are problems (including, perhaps,

some of the approximate counting problems for which the Sinclair-Jerrum techniques are effective) that are solvable in polynomial time using randomized algorithms, but cannot be solved in polynomial time using deterministic algorithms. More generally, what gap, if any, exists bet ween the efficiency of randomized and deterministic algorithms? The conventional wisdom in the 1970s was that there probably existed computational problems solvable in polynomial time by randomized algorithms, but requiring exponential time for deterministic solutions. This changed in the 1980s and 1990s with the development of the theory of pseudorandom generators, and a remarkable theorem of Impagliazzo and Wigderson [ 4], who proved that every randomized algorithm has a polynomial time “derandomization” (fully deterministic simulation), assuming a very plausible complexity-theory conjecture. The theory of pseudorandom generators arose from cryptography, and it is based on the notion of indistinguishability of distributions that provides the language to reason about the security of almost every cryptographic application. In this article we will explain what a

Pseudorandomness And Derandomization

The computational theory of pseudorandomness
and cryptography.
By Luca Trevisan

DOI: 10.1145/2090276.2090287

Randomized algorithms (that is, algorithms that make random choices at various points in their execution) are used to test the primality of large numbers, to perform approximate computations in complex
models arising in physics and in finance, to save memory in
“streaming” algorithms, to encrypt or authenticate messages
in cryptographic protocols, and in several other applications.

Since the 1970s, theoretical computer scientists have been wondering how necessary is the use of randomness in such applications.

In cryptographic applications, the use of randomness is necessary, at the very least in order to select passwords or secret keys that are difficult for an attacker to guess. Although it is an important question to determine how much randomness is necessary to guarantee a given level of security.

In algorithmic applications, it is
somewhat counterintuitive that ran-
domness would help at all. For example,
if I want to determine whether 20,988,
936,657,440,586,486,151,264,256,610,
222,593,863,921 is prime, which is a
question with a determined yes/no
answer, why should it help to make
random choices? The point is that one
can look at the problem of checking if
a number is prime as the problem of
looking for a “certificate” that a given
number n is composite; a non-trivial
divisor is clearly such a certificate, but
there are other ones, such as an integer
a such that an ≡⁄ a (mod n), or four dis-
tinct square roots (mod n) of the same
integer. Rabin, Solovay and Strassen [ 1,
2] proved that there is a good chance of
finding such certificates just by picking
them at random, even though no effi-
cient method to deterministically con-
struct them was known.
In this article, we will follow the
theoretical computer science conven-
tion of calling an algorithm “efficient”
if its running time is at most a polyno-
mial function of the length of the in-
put. When the input is an integer n, its
“length” is the number of bits in the bi-
nary representation of n, that is log2 n,
so an efficient algorithm for testing pri-
mality is an algorithm running in time
O((log n)c ) for some constant c. The al-
gorithms of Rabin and of Solovay and
Strassen are also efficient in the stan-
dard sense that they run reasonably
fast even on very large inputs.

Markov-Chain Monte Carlo methods, such as the Metropolis algorithm, are very effective randomized algorithmic techniques to find good approximations to problems arising in statistical physics and finance. As shown by Sinclair and Jerrum [ 3], such techniques can also be used to find approximate solutions to combinatorial counting problems, such as the problem