Friday, June 9, 2017

Course Overview

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

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: