Abstract:
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.
Speaker's Bio:
Avi Wigderson received his BSc degree from the Technion in 1980 and
his PhD degree from Princeton University in 1983, both in Computer Science.
From 1986 to 2003 he was on the faculty of the Computer Science Institute
at the Hebrew University. Since 1999 he is a Professor in the School of
Mathematics at the Institute for Advanced Study in Princeton. He has
held visiting positions at the University of California in Berkeley, IBM
Research in San Jose, the Mathematical Sciences Research Institute in
Berkeley, and Princeton University.
His research interests are complexity theory, algorithms, randomness
and cryptography. He is the recipient of the 1994 Nevanlinna Prize
presented at the International Congress of Mathematicians.
