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:**

- Complexity Theory - two brief surveys (by Oded Goldreich).
- Computational Complexity: A Conceptual Perspective (a book by Oded Goldreich, 2008).
- Modern Cryptography, Probabilistic Proofs and Pseudorandomness (by Oded Goldreich).
- Introduction to Complexity Theory - Lecture Notes (by Oded Goldreich, 1999 and 2002).

Back to the TOC at WIS page or to Oded Goldreich's homepage.