CS640A - Computational Complexity
Prerequisites:
3-0-0-9
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
Current Course Information
Instructor(s):
Number of sections:
Tutors for each section:
Schedule for Lectures:
Schedule for Tutorial:
Schedule for Labs: