Math & Cultural

All are invited to attend a lecture and panel discussion on “Beyond Computation: The P versus NP question” on May 9 from 5:30 p.m. till 7:30 p.m. at the Berkeley City College Auditorium. The speaker is Michael Sipser, a theoretical computer scientist and Professor of Mathematics at MIT. Additional panelists are Richard Karp, moderator (UC Berkeley), Ron Fagin (IBM Almaden), Russell Impagliazzo (UC San Diego), Sandy Irani (UC Irvine), Christos Papadimitriou (UC Berkeley), Omer Reingold (Microsoft Research), and Ryan Williams (Stanford University).

What are the theoretical limitations of computer power? In a remarkable 1956 letter, the great logician Kurt Gödel first raised this question when he asked the famous mathematician and computer pioneer John von Neumann whether certain computational problems could be solved without resorting to a brute force search through many possibilities. In so doing, he foreshadowed the P versus NP question, one of the major unanswered questions of contemporary mathematics and theoretical computer science. This question asks whether every problem whose solution can be easily verified by a computer can also be easily solved by a computer. An answer to this question would reveal the potential for computers to solve puzzles, crack codes, prove theorems, and optimize many practical tasks.

Michael Sipser has been on the faculty of MIT since 1980, where he was chairman of Applied Mathematics from 1998 to 2000. He has been head of the Mathematics Department since July 2004 and is also currently the interim Dean of Science. He was a research staff member at IBM Research in 1980, spent the 1985-86 academic year on the faculty of the EECS department at Berkeley and was a Lady Davis Fellow at Hebrew University in 1988. His research areas are in algorithms and complexity theory, specifically efficient error correcting codes, interactive proof systems, randomness, quantum computation, and establishing the inherent computational difficulty of problems. He is the author of the widely used textbook, Introduction to the Theory of Computation (Cengage, 2005).

This event is free and open to the public, but you must register to guarantee your seat in the auditorium. Seating is limited and first come, first served. Doors open at 5:00 p.m. Light refreshments will be served before the lecture. The event is sponsored by the Simons Institute for the Theory of Computing, Berkeley City College, MSRI, and the Simons Foundation.

More information and registration are available here.