Date: friday, 19.06.2009, 11:00
Speaker: prof. Avi Wigderson
Title: Randomness - a computational complexity view
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 crucial 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 counterpart
- Computational efficiency is crucial 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.
Program
| 19.06.2009 r. | |
| 09:30 | Laying flowers at the monument to the Polish cryptologists |
| 11:00 | Avi Wigderson Randomness - a computational complexity view |
Speaker
Professor Avi Wigderson from the School of Mathematics in the Institute for Advanced Study in Princeton is one of the most eminent and renowned computer scientists whose contributions to the theory of random algorithms, cryptography, and complexity theory have had major impact on modern computer science. Among many awards and honors obtained by Professor Wigderson is the Rolf Nevanlinna prize awarded to him at the International Congress of Mathematicians in Zurich.
