Tentative Outline

The following outline is planned before the semester starts. As the course goes, we will post the exact topics. See also the longer version with references.

  1. Introduction. Computation models. DTIME and P.

  2. NP, EXP, NEXP, co-NP.

  3. Diagonalization, time hierarchy.

  4. Space complexity, PSPACE, L, NL.

  5. Savitch’s Theorem. NL = coNL.

  6. Alternation. Polynomial hierarchy.

  7. Time vs Space vs Alternation.

  8. Circuits and formulas. Uniform. Time vs circuit size. Karp-Lipton Theorem. Branching programs.

  9. Randomness. Polynomial identity testing. ZPP, RP, BPP.

  10. BPP and other classes.

  11. Interaction. IP, AM, MA.

    (End of Sep)

  12. IP = PSPACE

  13. (Buffer)

  14. Cryptography

  15. PCP, hardness of approximation.

  16. NP in PCP(poly(n), 1)

  17. Derandomization. Pseudorandom generators.

  18. Nisan-Wigderson PRG.

    (End of Oct)

  19. Random walks, eigen values, expanders.UPATH in L.

  20. Extractors.

  21. Dinur’s Proof of PCP Theorem, 1

  22. Dinur’s Proof of PCP Theorem, 2

  23. (Buffer)

  24. Communication complexity

  25. Circuit lower bounds

  26. Natural proofs

    (End of Nov)

  27. #P

  28. Toda’s Theorem

Longer Outline

The following longer outline provides the materials of each lecture. [AB, xxx] denotes the chapter xxx of the Arora-Barak textbook, while [Sudan24, yyy] denotes the lecture yyy of the Lecture Notes of Sudan 2024.

  1. Introduction. Computation models. DTIME and P.

    • [AB, Chapt 1] [Sudan24, Introduction, Complexity Goals and Methods (2021 Notes, 2024 addendum, video, scribe.zip, scribe.pdf)]

  2. NP, EXP, NEXP, co-NP.

    • [AB, Chapt 2]

  3. Diagonalization, time hierarchy.

    • [AB, Chapt 3] [Sudan24, Diagonalization, Time/Space Hierarchy, Relativization (Notes, video, scribe.tex, scribe.pdf)]

  4. Space complexity, PSPACE, L, NL.

    • [AB, Chapt 4] [Sudan24, Space Complexity. PSPACE, L, NL. (2021 Notes - 1,2, video, scribe.tex, scibe.pdf) ]

  5. Savitch’s Theorem. NL = coNL.

    • [AB, Chapt 4] [Sudan24, Savitch’s Theorem. NL = CoNL. (2021 notes, video, scribe.zip, scribe.pdf) ]

  6. Alternation. Polynomial hierarchy.

    • [AB, Chapt 5] [Sudan24, Alternation. Time vs. Space vs. Alternation. Fortnow’s theorem. (2021 Notes, video, scribe.tex, scribe.pdf), More on Alternation. Debates. Polynomial Hierarchy. IHA. Karp-Lipton theorem. (2021 Notes, video, scribe.tex, scribe.pdf) ]

  7. Time vs Space vs Alternation.

    • [AB, Chapt 5] [Sudan24, Alternation. Time vs. Space vs. Alternation. Fortnow’s theorem. (2021 Notes, video, scribe.tex, scribe.pdf) ] [Williams25, https://arxiv.org/abs/2502.17779]

  8. Circuits and formulas. Uniform. Time vs circuit size. Karp-Lipton Theorem. Branching programs.

    • [AB, Chapt 6] [Sudan24, Circuits and Formulas. Time vs Circuit Size. Branching Programs. Lower bounds counting+ (2021 Notes, video, scribe.zip, scribe.pdf), More on Alternation. Debates. Polynomial Hierarchy. IHA. Karp-Lipton theorem. (2021 Notes, video, scribe.tex, scribe.pdf) ]

  9. Randomness. Polynomial identity testing. ZPP, RP, BPP.

    • [AB, Chapt 6] [Sudan24, Randomness. Promise problems. Randomized complexity classes: ZPP, RP, coRP,BPP. (2021 Notes, video, scribe.zip, scribe.pdf) ]

  10. BPP and other classes.

    • [AB, Chapt 7] [Sudan24, BPP contained in P/Poly. BPP contained in PH. (2021 Notes, video, scribe.tex, scribe.pdf) ]

  11. Interaction. IP, AM, MA.

    • [AB, Chapt 8] [Sudan24, Interaction. IP, AM, MA. (2021 Notes, video, scribe.zip, scribe.pdf) ]

    (End of Sep)

  12. IP = PSPACE

    • [AB, Chapt 8] [Sudan24, IP = PSPACE (2021 Notes, video, scribe.zip, scribe.pdf) ]

  13. (Buffer)

  14. Cryptography

    • [AB, Chapt 9]

  15. PCP, hardness of approximation.

    • [AB, Chapt 10] [Sudan24, Probabilistically checkable proofs. Inapproximability. (2021 Notes, video, scribe.zip, scribe.pdf) ]

  16. NP in PCP(poly(n), 1)

    • [AB, Chapt 10 ] [Sudan24, NP in PCP(poly(n),O(1)) (2021 Notes, video, scribe.zip, scribe.pdf) ]

  17. Derandomization. Pseudorandom generators.

    • [AB, Chapt 20] [Sudan24, Derandomization: Introduction to some goals (2021 Notes, video, scribe.tex, scribe.pdf) ]

  18. Nisan-Wigderson PRG.

    • [AB, Chapt 20] [Sudan24, The Nisan Wigderson Pseudorandom Generator (2021 Notes, video, scribe.zip, scribe.pdf) ]

    (End of Oct)

  19. Random walks, eigen values, expanders.UPATH in L.

    • [AB, Chapt 21]

  20. Extractors.

    • [AB, Chapt 21] [Sudan24, Trevisan’s Extractor (2021 Notes, video, scribe.zip, scribe.pdf) ]

  21. Dinur’s Proof of PCP Theorem, 1

    • [AB, Chapt 20] [Sudan24, Dinur’s proof of PCP theorem - 1 (2021 Notes, video, scribe.zip, scribe.pdf) ]

  22. Dinur’s Proof of PCP Theorem, 2

    • [AB, Chapt 20] [Sudan24, Dinur’s proof of PCP theorem - 2 (2021 Notes, video, scribe.tex, scribe.pdf) ]

  23. (Buffer)

  24. Communication complexity

    • [AB, Chapt 13]

  25. Circuit lower bounds

    • [AB, Chapt 14] [Sudan24, Parity vs. AC^0. (2021 Notes, video, scribe.tex, scribe.pdf) ]

  26. Natural proofs

    • [AB, Chapt 21]

    (End of Nov)

  27. #P

    • [AB, Chapt 17] [Sudan24, Toda’s Theorem: #P contains the PH (2021 Notes, video, scribe.tex, scribe.pdf) ]

  28. Toda’s Theorem

    • [AB, Chapt 17] [Sudan24, Proof of Toda’s theorem. (2021 Notes, video, scribe.zip, scribe.pdf) ]