CS 6520, Computational Complexity : Home Page

CSCI-GA.3033-118 Spring 2026

Special Topics: Computational Complexity

General Information and Announcements

Prerequisites

Prior knowledge of following materials is assumed. A brief overview of basics will be given in the first lecture. Other than this, the course should be self-contained.

Discrete math and probability.
Data structures : lists, trees, stacks etc.
Algorithms, asymptotic running time, basic algorithms like breadth/depth-first search, sorting etc.
Finite automata (deterministic and non-deterministic), regular languages, context free languages.
Turing machines, decidability, NP-completeness, reductions.

References for this basic material are :

M. Sipser : Introduction to the theory of computation.
T. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein : Introduction to Algorithms (Second Edition).

Administrative Information

Lectures: Tu 12:30-2:30, CIWW 202

Professor: Subhash Khot – WWH 416 , 212-998-4859, Office hours: TBA

Course Syllabus

The first part of the course will cover basic aspects of complexity theory. This includes complexity classes P, NP, L, NL, PSPACE, Polynomial Hierarchy, BPP, P/poly, NC, IP, AM, #P and relationships among them.

The second part of the course will cover advanced toipcs, e.g. PCPs, circuit lower bounds, communication complexity, derandomization, property testing and quantum computation. The emphasis will be on breadth rather than covering any of these topics in depth.

Homeworks and Exams

Tentative:

Towards the end of the course, you will be required to read one research paper of your choosing. The list of papers/topics will be made available.

References and Textbooks

We will not "follow" any particular textbook, but a good reference is: Arora and Barak: Computational Complexity: A Modern Approach.

A draft of this book is available at http://www.cs.princeton.edu/theory/index.php/Compbook/Draft.

You may also want to refer to :

C.H. Papadimitriou : Computational Complexity.
D.Z. Du and K.I. Ko : Theory of Computational Complexity.

Course notes from similar courses taught at Princeton and UC-Berkeley may be useful. See :