Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites:  

Course Contents

Introduction to Computational Complexity. Complexity Classes. P and NP completeness. Hierarchy Theorems. Space Complexity. NL completeness. Savitchs Theorem. Immerman zelepsćenyi Theorem Polynomial Hierarchy. Alternating Turing Machines. Time Space Trade off for SAT. Circuit Complexity. Polynomial sized circuits. Uniformity. Circuit classes NC and AC. Randomized Computations. RP, BPP, ZPP. Relationship between BPP and other classes. Randomized space complexity. Interactive Proofs. Various protocols. IP PSPACE. Quantum Computation. The class BQP. Grovers search algorithm. Introduction to PCP and Hardness of Approximation. NP ⊆ PCP (poly(n), 1) Communication Complexity. Definition and lower bound techniques. Circuit Lower Bounds. Lower bounds on AC0. Counting Complexity. The class #P. Todas Theorem. Tentative Topics (depending on availability of time). Hardness Amplification and Error Correcting Codes. Derandomization. Average case complexity. 

Topics