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
§§§
Abstract:
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.
§§§
Bio:
Research Interests:
- Complexity Theory, Algorithms, Randomness and Cryptography
Honors:
- 1994 Nevanlinna Prize, International Congress of Mathematicians, Zurich.
Education:
- 1980 - 1983 Ph.D. in Computer Science, Princeton University
- 1977 - 1980 B.Sc in Computer Science, Technion, Haifa, Israel
Permanent Positions:
- 1999 - Institute for Advanced Study, Princeton
- 1986 - 2003 Computer Science Institute, Hebrew University, Jerusalem
Visiting Positions:
- 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).
