Course Overview

CS 6520 Computational Complexity

Fall 2015

Instructor: Lance Fortnow

Time: MWF 9:05-9:55

Room: Klaus 1456

Description: This course will give an overview of advanced topics in computational complexity including the P versus NP problem, the structure of NP, the polynomial-time hierarchy, circuit complexity, randomness, counting, interactive and probabilistically checkable proofs.

Detailed list of topics

Prerequisites: A basic knowledge of Turing machines and the P v NP problem at the level of CS 4510.

Textbook: None. Computational Complexity by Arora and Barak cover much of the material from the course but we won't be following them.

Coursework: Assignments roughly every other week. This is a theoretical course and assignments will be problem solving and will not involve any programming.

Course Website: gtccf15.blogspot.com