Introduction to Computational Complexity (Fall 2023)
Course Number: COMS 4236
Date/Time: MW 1:10-2:25pm
Room: Mudd 524
First meeting: September 6
This Week’s Office Hours (updated every Sunday)
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.
All problem sets will be available on this Overleaf [link]: All solutions must be submitted on Gradescope.
- Pset0, due September 13.
- Pset1, due September 27.
- Pset2, due October 15.
- Pset3, due November 15.
- Pset4, due December 1.
All Zoom recordings are on CourseWorks
- Week 1
- September 6. Intro to complexity, course overview, computational problems and computational models. [Slides]
- Helpful reading: Arora-Barak Ch. 1, Sipser Ch. 3.
- Week 2
- Week 3
- Week 4
- Week 5
- Week 6
- Week 7
- Week 8
- Week 9
- Week 10
- November 8. Permanent, random self-reducibility. [Slides]
- Week 11
- Week 12
- Helpful reading: Arora-Barak Chapter 8
- November 20. Interactive proofs. [Slides]
- Week 13
- Week 14
- Helpful reading: Arora-Barak Chapter 11.
- December 4. Probabilistically checkable proofs. [Slides]
- December 6. Probabilistically checkable proofs.