CS 6520 Computational Complexity
Fall 2017
Instructor: Lance Fortnow
Time: MWF 9:05-9:55
Room: Whitaker Biomedical Engineering 1103
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 strong mathematical background and a basic knowledge of Turing machines and the P v NP problem at the level of CS 4510. This is a course meant for advanced students with a strong interest in theoretical computer science--if you just want to fulfill the graduate theory requirement you should take CS 6505.
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. There are no exams.
Course Website: gtcc17.blogspot.com