Complexity Theory (Monsoon 2024)

Course Material

(Lecture notes are uploaded in the “Google classroom” for the course. Drop me an email if you want to access them.)

Assignments

Textbooks

  • Introduction to the Theory of Computation
    • by Michael Sipser
    • Cengage India, 2014 (ISBN-13: 978-8131525296)
  • Computational Complexity: a modern approach
    • by Sanjeev Arora and Boaz Barak
    • Cambridge University Press, 2009 (ISBN-13: 978-0521424264)
    • Online draft (2007) from Princeton University

References

  • Mathematics and Computation: A Theory Revolutionizing Technology and Science
    • by Avi Wigderson
    • Princeton University Press, 2019 (ISBN-13: 978-0691189130)

Course Plan

(Note: Topics within the modules might change)

  • Module 1: Time, Space and Non-determinism
    • Broad goal: Understanding computation with bounded resources, in particular time, space and non-determinism. Properties of and open questions about problems computable with bounded resources.
    • Topics: Review of Turing machines, time complexity and the class P. The class NP, reductions and complete problems. Space complexity, Savitch’s theorem, PSPACE, Log-space computation and directed reachability.
  • Module 2: Complexity Classes and Circuits
    • Broad goal: Defining complexity classes and proving bounds on those classes. Computing with oracles and difficulty of resolving P vs NP with Turing machines. Basics of circuit complexity.
    • Topics: Intractability and lower bounds, hierarchy theorems. Polynomial hierarchy and Turing machines with oracles. Motivation for studying circuits and some elementary results.
  • Module 3: Randomized Computation
    • Broad goal: Viewing randomness as a computational resource, understanding its power and scope.
    • Topics: Probabilistic machines, the class BPP. Polynomials, the Schwarz-Zippel lemma, and the classes RP, coRP and ZPP. Error reduction and derandomization of probabilistic algorithms.
  • Module 4: Interactive Proofs (IP)
    • Broad goal: Understanding how (and how much) interaction with a more powerful machine can help in computation.
    • Topics: IP in relation to NP, public vs private randomness, the classes AM and MA. Tools for designing interactive protocols. Power of IP, a protocol for the permanent.
  • Module 5: Overview of subfields (optional, if time permits)
    • Broad goal: A (very) high level overview of some areas of research within complexity theory.
    • Areas: Boolean circuit complexity, communication complexity, algebraic complexity.