Avi Wigderson Discusses Computational Efficiency and the Limits of Human Knowledge

The mathematical study of the power and limits of efficient computation is the domain of theoretical computer science. Central to this study is the relationship between two classes of computational problems called "P" and "NP"; understanding this relationship is a major outstanding problem of computer science and mathematics. Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study, will provide insights into this relationship in his talk, The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human Knowledge. The lecture will take place on Friday, October 24, at 6:00 p.m. in Wolfensohn Hall on the Institute's campus.

In his talk, Professor Wigderson will attempt to describe the problem's technical, scientific and philosophical content, its status and the implications of its two possible resolutions.

Wigderson, who joined the Faculty of the Institute in 1999, received his undergraduate education in computer science at the Technion-Israel Institute of Technology. He received his Ph.D. in computer science from Princeton University in 1983. Wigderson came to the Institute from the Computer Science Institute of The Hebrew University in Jerusalem, where he was a professor. Among his other positions, he was Chairman of the Computer Science Institute of The Hebrew University (1993-95), served on the faculty at Princeton University as Visiting Associate Professor (1990-92) and Visiting Professor (1995-96), and was a Fellow at the Mathematical Sciences Research Institute in Berkeley, California (1985-86).

Wigderson is a widely recognized authority in the diverse and evolving field of theoretical computer science. His main research area is computational complexity theory. Other research interests include algorithms, randomness, cryptography, discrete mathematics and parallel and distributed computation. Wigderson and Visiting Professor in the School of Mathematics Russell Impagliazzo represent the Institute as part of a team of researchers that will share in a recent $10 million Expeditions in Computing grant from the National Science Foundation to advance research and education in the study of computational intractability. The team also includes members from Princeton University; Rutgers, The State University of New Jersey and New York University.

Among his awards and honors, Wigderson received the 1994 Rolf Nevanlinna Prize, awarded once every four years by the International Congress of Mathematicians. He was also selected to present the prestigious AMS Josiah Willard Gibbs Lecture at the 2008 Joint Mathematics Meetings in San Diego, and shared the 2008 Levi L. Conant Prize, awarded annually by the American Mathematical Society.

For further information about this event, which is free and open to the public, please call (609) 734-8175, or visit the Public Events page on the Institute website, www.ias.edu.