Some Insights of Computational Complexity Theory


Avi Wigderson

Institute for Advanced Study and
Institute for Computer Science, Hebrew University


Harvard University

Thursday, May 3, 2001


Talk at 4:30 p.m. in Science Center D

Tea at 4:00 p.m. in the Math Lounge


Abstract:   Computational complexity theory has been one of the most exciting fields of scientific research over the last few decades. This research studies the power of feasible computation, and is guided by a few clear and focused questions, deeply motivated on scientific, practical and philosophical grounds, like the P vs NP problem, and the questions on the power of randomized and quantum computation.

While these problems are far from resolved, Complexity Theory was able to offer fresh rigorous definitions to some central notions which naturally (or less so) arise from these questions, and unveil many rich and beautiful connections between them.

In this general survey, I would like to probe some of the unique features and insights of the complexity theory viewpoint. This will be done by considering how (and why) notions which intrigued people for centuries or even millenia (like Knowledge, Randomness, Cryptography, Learning, Proof, and naturally, Computation), reveal new dimensions, and are suprisingly linked together, when viewed from our special Computational Complexity glasses.


Home Web page:  Alexandru I. Suciu  Comments to: 
Created: April 24, 2001    URL: