CS 6520, Computational Complexity : Home Page

CSCI-GA.3350-001

Theory of Computation (Honors)
Subhash Khot

Spring 2014

General Information and Announcements

Homework 3 (due April 28) and Endterm (due May 12) available. A short (= 2 page) report on your reading project (= one research paper from the list below) is also due May 12. No extensions on any of these deadlines.

Solutions to Homework 1,2 and midterm are available.

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

Administrative Information

Lectures: MW 3:30-4:45, WWH 312

Professor: Subhash Khot – Off 416, 212-998-4859, Office hours : Just before the class or by appointment.

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

There will be three homeworks, a take-home midterm and a take-home endterm.

Towards the end of the course, you might be required to read one research paper of your choosing and present it in class. The list of recommended papers/topics appears above.

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 :