Events Spring 2014

Beyond Computation: The P versus NP question

May 9, 2014 5:30 pm – 7:30 pm 

Add to Calendar

Location: 
Berkeley City College Auditorium: 2050 Center Street, between Shattuck Ave. & Milvia St., in Berkeley (near the Downtown Berkeley BART station)

Speaker:

Michael Sipser (Massachusetts Institute of Technology)

Additional panelists:

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.

The event begins with a talk on the P vs NP question, by Professor Michael Sipser of MIT. This will be followed by a panel discussion, in which a group of distinguished computer science theorists will join Sipser to illuminate the current status of the question and our prospects for resolving it. Light refreshments will be served before the lecture, at 5 p.m.

 

About Michael Sipser:

Dr. Michael Sipser is a theoretical computer scientist, member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and Professor of Mathematics at MIT. He received a PhD in Engineering from the University of California, Berkeley in 1980 under the supervision of Manuel Blum in the EECS Department, and a BA in Mathematics from Cornell University in 1974.

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

His distinctions include the MIT Graduate Student Council Teaching Award, 1984, 1989 & 1991, and the MIT School of Science Student Advising Award, 2003. He is a Fellow of the American Academy of Arts and Sciences.

 

Simons Institute for the Theory of ComputingMathematical Sciences Research InstituteBerkeley City College

Video:


Part 1 of 2
Download Video [3.42GB .mp4]


Part 2 of 2 (panel discussion)
Download Video [2.65GB .mp4]

Register to attend:

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 p.m.

The registration deadline for "Beyond Computation: The P versus NP question" has now passed. Tickets may be available at the door. For questions about registration please contact Caroline Allum at +1.510.664.9856 or simonsevents [at] berkeley [dot] edu (subject: Beyond%20Computation%3A%20The%20P%20versus%20NP%20question) .