THIS PAGE IS NO LONGER UPDATED.
Computational Complexity Theory is a central field of Theoretical Computer Science, with a remarkable list of celebrated achievements as well as a very vibrant present research activity. The field is concerned with the study of the intrinsic complexity of computational tasks, and this study tend to aim at generality: It focuses on natural computational resources, and the effect of limiting those on the class of problems that can be solved.
The Department of Computer Science at the Weizmann Institute of Science maintains a wide range of activities in Computational Complexity. Specific areas of interest include Arithmetic Complexity, Circuit Complexity, Communication Complexity, Complexity of Approximation Problems, Cryptography, Probabilistic Proof Systems, Proof Complexity, and Pseudorandomness. The list of faculty members that are actively interested in complexity theory includes Irit Dinur, Uriel Feige, Oded Goldreich, Shafi Goldwasser, Robert Krauthgamer, Moni Naor, Ran Raz, Omer Reingold and Adi Shamir.
Relevant material available on-line:
Back to the TOC at WIS page or to Oded Goldreich's homepage.