Event
Randomness, Computation and Proof

Avi Wigderson

September 27, 2007 3:00 PM  to 
September 27, 2007 4:00 PM
Room 1235

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

This event is part of Distinguished Lecture Series.

Meeting Type
Lecture

Contacts
Dawn Patterson, (703)292-8910 x7097 dpatters@nsf.gov
       Preferred Contact Method: Email

NSF Related Organizations
National Science Foundation
Division of Computing and Communication Foundations