A. Wigderson
Institute for
Advanced Study
Man has grappled with the meaning and utility of randomness for
centuries. Research in the Theory of Computation in the last thirty
years has enriched this study considerably. I'll describe two main
aspects of this research on randomness, demonstrating its power and
weakness respectively.
- Randomness is paramount to computational efficiency:
The use of randomness can dramatically enhance computation (and do
other wonders) for a variety of problems and settings. In particular,
examples will be given of probabilistic algorithms (with tiny error)
for natural tasks in different areas of mathematics, which are
exponentially faster than their (best known) deterministic
counterparts.
- Computational efficiency is paramount to understanding randomness:
I will explain the computationally-motivated definition of
"pseudorandom" distributions, namely ones which cannot be
distinguished from the uniform distribution by any efficient procedure
from a given class. We then show how such pseudorandomness may be
generated deterministically, from (appropriate) computationally
difficult problems. Consequently, randomness is probably not as
powerful as it seems above.
I'll conclude with the power of randomness in other computational
settings, primarily probabilistic proof systems. We discuss the
remarkable properties of Zero-Knowledge proofs and of
Probabilistically Checkable proofs.