Document Actions
Distinguished Lecture: Avi Wigderson, Professor at the School of Mathematics, Institute for Advanced Study
(Princeton University and Institute for Advanced Study)
The Art of Reduction
| What | Distinguished Lecture Colloquium |
|---|---|
| When |
Nov 19, 2008 04:15 PM
Nov 19, 2008 05:15 PM
Nov 19, 2008 from 04:15 pm to 05:15 pm |
| Where | 129 Waring |
| Contact Name | Adam Smith |
| Contact email | asmith@cse.psu.edu |
| Contact Phone | 863-0076 |
| Add event to calendar |
vCal
iCal
|
Everyone is familiar with NP-completeness, and the basic idea that appropriate reductions can tie together seemingly unrelated computational problems. The last couple of decades have seen an incredible growth and sophistication in utilizing reductions and completeness. These tie together seemingly unrelated computational notions, models and even whole subareas of computer science. I will survey such results, and their general and diverse consequences.
The talk will not assume any specific advanced knowledge in math or computer science, and should be accessible to graduate students in both departments.
Bio:
Professor at the School of Mathematics, Institute for Advanced Study. He obtained his B.Sc. in Computer Science from the Technion in 1980, and his Ph.D. from Princeton in 1983. He was a member of the faculty at the Hebrew University in Jerusalem from 1986-2003, and is currently a member of the Mathematics Faculty at the Institute for Advanced Study at Princeton. His research interests lie principally in Complexity Theory, Algorithms, Randomness, and Cryptography. His awards include the Nevanlinna Prize for outstanding contributions in Mathematical Aspects of Information Sciences (2004).
