Course Description

This course introduces students to computational complexity, which is the study of how the resources required to solve a computational problem scale with the problem's size. Central to this theory is the notion of complexity classes, which are sets of computational problems that behave similarly in terms of their resource requirements. By the end of this course, the successful student will have developed a solid understanding for where in a hierarchy — ranging from easy to moderately hard to intractable to unsolvable — a given computational problem falls.

The basic plan is to study five key aspects of computation:

• time,
• space,
• nondeterminism,
• randomness, and
• interaction.

The goal is to understand the power of each of these. Time permitting, we shall tackle additional topics, such as arithmetic complexity or the basics of quantum computation.

Prerequisites

Ideally, a student in this course will have taken an introductory Theory of Computation course, such as Dartmouth's CS 39. In principle, a student with good mathematical maturity can take this course after some self-study to read up on the basics of the Turing Machine model and the notion of NP-completeness (familiarity with these two things will be expected).

Course Staff

Professor: Amit Chakrabarti

Teaching Assistant: Ankita Sarkar

Textbooks and Sources

There is no set textbook for the course, so it is vital to attend class. However, there are three reference books that cover just about everything we shall do in class, and I will be updating the schedule table with appropriate references. These reference books are:

• Introduction to the Theory of Computation (Second Edition). Michael Sipser. Referred to as [Sip] in the course materials.
• Computational Complexity. Christos Papadimitriou. Referred to as [Pap].
• Complexity Theory: A Modern Approach. Sanjeev Arora and Boaz Barak. Draft available online. Referred to as [AB].

Work and Assessment

The assessed work in the course consists of (a) solving several homework problems, spaced out throughout the term; (b) a mid-term exam; (c) either a final project (term paper) or a final exam, TBD. Many—but not all—homework problems will be challenging. For details, please see the administrivia tab.