Modern Complexity Theory
Bouquet Core / Elective
Instructor
Girish Varma, CSTAR and MLL
Teaching Assistants
Athreya Chandramouli, Sumit Kumar Jha
Requirements
Discrete Maths, Probability, Linear Algebra, Data Structures and Algorithms.
Course Topics
- Intro to Proofs
- Administrivia
- Social Choice | Arrows Theorem
- Turing Machines
- Encodings, TMs, Recursive Languages
- TM for Palindrome and Running Time
- Lowerbounds for 1 Tape TMs
- Cantor, Church, Turing, Godel
- Universal TMs and Halting Problem
- Undecidability | Halting Problem | DTIME
- Lowerbounds for 1 Tape TMs
- NP Hardness
- 2CNF Algorithm
- NP Verification
- Cook-Levin Theorem
- Polynomial Hierarchy
- Space and Circuit Complexity
- LSPACE | PSPACE | Completeness
- Circuit Model
- Karp - Lipton Theorem
- Randomized Computation
- Randomized Algorithms Examples
- RP | CoRP | BPP | Robustness | Chernoffs
- Derandomization | Adleman's Theorem | Method of Conditional Probabilities
- Quantum Computing