Computational Complexity Theory 

Computational Complexity Theory is the study of how much of a given resource (such as time, space, parallelism, randomness, algebraic operations, communication, quantum steps, or proof length) is required to perform the computations that interest us the most. Four decades of fruitful research have produced a rich and subtle theory of the relationship between different resource measures and problems. At the core of the theory are some of the most alluring open problems in mathematics.

The Graduate Summer School in Computational Complexity will consist of intensive short courses offered by the leaders in the field; these lectures will not duplicate standard courses available elsewhere. The courses will assume little, but provide a rapid and efficient development of many of the recent highlights of complexity theory. These courses are perfectly suited to graduate students, but it is anticipated that they will also be of interest to senior researchers in computer science and mathematics.

We will assume little more than a standard undergraduate preparation in mathematics or computer science. It would be helpful to look at Christos Papadimitriou’s book "Computational Complexity" before attending the courses.

Participants in the Graduate Summer School may wish to become involved in the Undergraduate Program, audit parts of the Research Program, or participate in the programs of the Education component. Graduate students also are expected to participate in Institute-wide activities such as the "Cross Program Activities."

For more detailed information about the courses of the Graduate Summer School:

Graduate Summer School Course Abstracts

The application process is now closed.

Return to IAS/PCMI Summer Session 2000

Return to IAS/PCMI Home Page

This page is archival material of the IAS/Park City Mathematics Institute