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
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