About the series
CISE Distinguished Lecture
Thursday, September 27th, 2007 at 3:00pm, Rm. 1235*
Randomness, Computation and Proof
Professor Avi Wigderson
Institute for Advanced Studies, Princeton
The concepts in the title play a role in almost everybody's life, and have intrigued mathematicians for many centuries. Work by Goedel, Turing, von Neumann and others, in the first half of the 20th century, brought, besides the computer revolution, a new understanding of these concepts, and new connections between them.
In this talk I'll explain some work in theoretical computer science, done in the second half of the 20th century, which led to further understanding, more connections and basic problems about these notions. These developments include the immense power of probabilistic proofs, the surprising weakness of computational randomness, the P versus NP problem and its meaning for science and human knowledge. Key to these developments is Computational Complexity - the field exploring the difficulty of computational problems.
The talk is designed for scientists of all disciplines.
- Complexity Theory, Algorithms, Randomness and Cryptography
- 1994 Nevanlinna Prize, International Congress of Mathematicians, Zurich.
- 1980 - 1983 Ph.D. in Computer Science, Princeton University
- 1977 - 1980 B.Sc in Computer Science, Technion, Haifa, Israel
- 1999 - Institute for Advanced Study, Princeton
- 1986 - 2003 Computer Science Institute, Hebrew University, Jerusalem
- 1995 - 1996 Institute for Advanced Study and Princeton University
- 1990 - 1992 Princeton University
- 1985 - 1986 Mathematical Sciences Research Institute, Berkeley, California
- 1984 - 1985 IBM Research, San Jose, California
- 1983 - 1984 U.C Berkeley, California
* If you would like to arrange a meeting with Prof. Wigderson, please contact Dawn Patterson (ext. 7097).