# Modern Complexity Theory

Bouquet Core / Elective

Enrollment in this course is by invitation only

## 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
- Interactive Computation
- Probabilistically Checkable Proofs
- PCP characterization of NP | Hardness of Approximation
- Succint Proofs | SNARKS