Avi Wigderson

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.