(1) 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.
(2) 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.
Bio: Avi Wigderson is a Professor in the School of Mathematics at the Institute for Advanced Studies, Princeton. He was with the Computer Science Institute, Hebrew University, Jerusalem from 1986 until 2003. He received his Ph.D. in Computer Science in 1983 from Princeton University. His main research interests are in complexity theory, algorithms, randomness, and cryptography. Prof. Wigderson has received the Nevanlinna Prize, the Yoram Ben-Porat Presidential Prize for Outstanding Researcher, the Conant Prize, and the Godel Prize.
Refreshments will be provided at 10:45
This talk is part of the URCS Distinguished Speaker Series.