Randomness - A Computational Complexity View

Jump to other IT Society Websites:

Randomness - A Computational Complexity View


 Avi Wigderson

Professor Avi Wigderson
Institute for Advanced Study
Princeton University


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 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.



broadband-medium broadband-high full
mp4 mp4 mp4wmv





Friday, July 11, 2008


Avi Wigderson is a Professor at the School of Mathematics, Institute for Advanced Study, Princeton, New Jersey. His research interests include complexity theory, parallel computation, combinatorics and graph theory, algorithms, randomness and cryptography, and neural networks. He has held visiting positions at Princeton University, the Mathematical Sciences Research Institute in Berkeley, IBM Research in San Jose, and the University of California at Berkeley. He is a recipient of a 2008 Conant Prize and the 1994 Nevanlinna Prize.