Patterns hidden from
By Madhu Sudan
IS ThE numBER 9021960864034418159813
random? Educated opinions might
vary from “No! No single string can be
random,” to the more contemptuous
”Come on! Those are just the 714th
to 733rd digits of π.” Yet, to my limited mind, the string did appear random. Is there a way to use some formal
mathematics to justify my naïveté?
The modern theory of pseudorandomness2, 5 indeed manages to explain such
phenomena, where strings appear random to simple minds. The key, this
theory argues, is that randomness is
really in the “eyes of the beholder,” or
rather in the computing power of the
tester of randomness. More things appear random to simpler, or resource-limited, algorithms than to complex,
Why should we care? Because randomness is a key resource in computation. Monte Carlo simulations abound
in the use of computation for prediction. On the theoretical side too, algorithms get simplified or speeded
up incredibly if they use randomness.
Fundamental tasks in distributed
computing (such as synchronization)
can be solved only with randomness.
And there is no hope for maintaining
privacy and secrecy without randomness. At the same time much of the randomness we deal with in reality is not
“pure.” They don’t come as a collection
of independent random bits, but are
generated by other processes. Knowing
how an algorithm, or a computational
process, works in the presence of somewhat random strings becomes the essence of a recurring question. (For example, should you really trust nuclear
power safety calculations made by a
Monte-Carlo algorithm using randomness from the C++ rand program?)
Such questions get formalized in
the theory of pseudo-randomness
as follows: It considers some source
of randomness X (formally given by
some probability distribution over
n-bit strings), and a class of Boolean
algorithms A (algorithms that decide
Boolean questions) and asks if some
algorithm in A behaves very differently
given access to a random string gener-
ated by X, than it does on pure random
strings? If every algorithm in A behaves
roughly the same on X as on pure ran-
domness, we say X is pseudo-random
to A. In the example here, X = Xπ may be
the source that picks a random integer
i between 1 and 10000 and outputs π
[i + 1]; . . . ; π [i + 20] where π [j] denotes
the jth digit of π. Given some class of
algorithms A one could now ask, does
Xπ look pseudo-random to A?
1. bazzi, l.M. J. Polylogarithmic independence can fool dnf
formulas. SIAM J. Comput. 38, 6 (2009), 2220-2272.
2. blum, M. and Micali, s. how to generate
cryptographically strong sequences of pseudorandom
bits. SIAM J. on Computing 13, 4 (nov. 1984), 850-864.
3. linial, n. and nisan, n. approximate inclusion-exclusion. Combinatorica 10, 4 (1990), 349-365.
4. nisan, n. Pseudorandom generators for space-bounded
computation. Combinatorica 12, 4 (1992), 449-461.
5. yao, a.c-c. theory and applications of trapdoor
functions (extended abstract). In Proceedings of FOCS
(1982). Ieee, 80-91.
Madhu Sudan ( email@example.com) is a Principal researcher
at Microsoft research new england and the Fujitsu
Professor of electrical engineering and computer science
at the Massachusetts Institute of technology.
© 2011 acM 0001-0782/11/04 $10.00