Skip to main content

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

  1. Intro to Proofs
    1. Administrivia
    2. Social Choice | Arrows Theorem
  2. Turing Machines
    1. Encodings, TMs, Recursive Languages
    2. TM for Palindrome and Running Time
    3. Lowerbounds for 1 Tape TMs
  3. Cantor, Church, Turing, Godel
    1. Universal TMs and Halting Problem
    2. Undecidability | Halting Problem | DTIME
    3. Lowerbounds for 1 Tape TMs
  4. NP Hardness
    1. 2CNF Algorithm
    2. NP Verification
    3. Cook-Levin Theorem
    4. Polynomial Hierarchy
  5. Space and Circuit Complexity
    1. LSPACE | PSPACE | Completeness
    2. Circuit Model
    3. Karp - Lipton Theorem
  6. Randomized Computation
    1. Randomized Algorithms Examples
    2. RP | CoRP | BPP | Robustness | Chernoffs
    3. Derandomization | Adleman's Theorem | Method of Conditional Probabilities
  7. Quantum Computing
  8. Interactive Computation
  9. Probabilistically Checkable Proofs
    1. PCP characterization of NP | Hardness of Approximation
    2. Succint Proofs | SNARKS
  1. Course Number

    M20Temp11
  2. Classes Start

    Monsoon 2020
  3. Classes End

  4. Estimated Effort

    10-12 Hrs per Week