Introduction to Computational Complexity (Fall 2023)

Jan 1, 0001

Course Number: COMS 4236
Date/Time: MW 1:10-2:25pm
Room: Mudd 524
First meeting: September 6

Syllabus

This Week’s Office Hours (updated every Sunday)

Description

Many computational problems(such as multiplying two numbers, or sorting a list of numbers) are known to be “easy” in the sense that we have efficient algorithms for them. Unfortunately, many other computational problems of great importance (such as factoring large numbers, or finding the shortest tour that passes through all the cities on a map) seem to be difficult. Are these problems really inherently difficult – do no efficient algorithms exist, or do we just need to come up with cleverer algorithms that can solve these problems efficiently?

Questions such as these lie at the heart of computational complexity, which is the study of inherent abilities and limitations of efficient computation. Computational complexity is one of the most fundamental and important topics in computer science; indeed, the core question of computational complexity theory (P vs NP) is one of the most famous and important open questions in all of computer science and mathematics.

Tentative list of topics: time and space complexity, nondeterminism, Cook-Levin, Ladner’s theorem, Polynomial Hierarchy, Nonuniformity, Relativization, Time-Hierarchy Theorems, Savitch’s theorem PSPACE-Completeness, randomized computation, counting complexity, interactive proofs, PCP theorem and the hardness of approximation, meta-complexity.

Problem Sets

All problem sets will be available on this Overleaf [link]: All solutions must be submitted on Gradescope.

  1. Pset0, due September 13.
  2. Pset1, due September 27.
  3. Pset2, due October 15.
  4. Pset3, due November 15.
  5. Pset4, due December 1.

Schedule

All Zoom recordings are on CourseWorks

  1. Week 1
    • September 6. Intro to complexity, course overview, computational problems and computational models. [Slides]
    • Helpful reading: Arora-Barak Ch. 1, Sipser Ch. 3.
  2. Week 2
    • Helpful reading: Arora-Barak Ch. 1, 2, Sipser Ch. 3, 7.
    • September 11. Time, space, nondeterminism, P, NP. [Slides]
    • September 13. Co-classes, reductions, NP completeness. [Slides]
  3. Week 3
    • Helpful reading: Arora-Barak Ch. 2, 3.
    • September 18. Cook-Levin, Diagonalization, Time Hierarchy Theorem. [Slides]
    • September 20. Time, Space, Non-deterministic Hierarchy Theorems. [Slides]
  4. Week 4
    • Helpful reading: Arora-Barak Ch 3, 5.
    • September 25. Oracles and Baker-Gill-Solovay. [Slides]
    • September 27. Polynomial Hierarchy. [Slides]
  5. Week 5
    • Helpful reading: Arora-Barak Ch 6.
    • October 2. Nonuniformity, circuits, advice. [Slides]
    • October 4. Circuits and Karp-Lipton theorem. [Slides]
  6. Week 6
    • Helpful reading: Arora-Barak Ch 4.
    • October 9. Space complexity. [Slides]
    • October 11. Space complexity, Savitch's theorem, NL-completeness. [Slides]
  7. Week 7
    • Helpful reading: Arora-Barak Ch 4 (for Immerman-Szelepcsenyi) and Ch 7.
    • October 16. Immerman-Szelepcsenyi (NL = coNL). Randomized computation, probability basics. [Slides]
    • October 18. Tail bounds. Polynomial identity testing. [Slides]
  8. Week 8
    • Helpful reading: Arora-Barak Ch 7.
    • October 23. Some randomized algorithms, randomized complexity classes. [Slides]
    • October 25. Properties of RP, ZPP, BPP. [Slides]
  9. Week 9
    • Helpful reading: Arora-Barak Chs 7 and 17.
    • October 30. Randomness versus nonuniformity, BPP and poly-time hierarchy, start counting. [Slides]
    • November 1. Complexity of counting problems: basics, completeness, permanent. [Slides]
  10. Week 10
    • November 8. Permanent, random self-reducibility. [Slides]
  11. Week 11
    • Helpful reading: Arora-Barak Chapter 17.
    • November 13. Finish random self-reducibility of permanent. [Slides]
    • November 15. Approximate counting. FPRAS for #DNF, no FPRAS for #CYCLES, NP-oracle gives FPRAS for all of #P. [Slides]
  12. Week 12
    • Helpful reading: Arora-Barak Chapter 8
    • November 20. Interactive proofs. [Slides]
  13. Week 13
    • Helpful reading: Arora-Barak Chapter 8.
    • November 27. Public-coin protocols for set size lower bounds, graph non-isomorphism. [Slides]
    • November 29. $\mathsf{IP} = \mathsf{PSPACE}$. [Slides]
  14. Week 14
    • Helpful reading: Arora-Barak Chapter 11.
    • December 4. Probabilistically checkable proofs. [Slides]
    • December 6. Probabilistically checkable proofs.