Introduction to Computational Complexity, Fall 2025
General Information:
Teaching Assistants:
-
Arman Ozcan, Office hours: Friday 11am-12pm, Location: Zoom (links on courseworks), Email: ao2794@columbia.edu
-
Hao Cui, Office hours: Monday 4pm-5pm, Location: CS TA room in Mudd, Email: hc3377@columbia.edu
Course Description:
- In this course, we study Computational Complexity, one of the most active research areas of Theoretical Computer Science devoted to "understanding" the intrinsic hardness of computational problems / limitations of efficient algorithms. We will mostly follow the book of Sipser. Below is a list of topics we plan to cover in the course:
- Diagonalization: Undecidability, time and space hierarchies
- Basic complexity classes (P, NP, PSPACE ...)
- Reductions and completeness
- Interactive proofs: IP = PSPACE
- Randomness as a resource and related complexity classes
- Probabilistically checkable proofs and inapproximability
- Nonuniform computational models
- Decision tree lower bounds
- Communication complexity
- Circuit lower bounds
Prerequisites:
-
An introductory course on theory of computation, e.g., COMS 3261.
- A course on algorithms, e.g.,
COMS 3137/3139 or 4231, will be helpful but is not required. The course is mostly theoretical, so you should feel comfortable reading and working with
math and proofs (Chapter 0 of Sipser's book is a good resource.) and general mathematical maturity will be assumed. Some knowledge of discrete mathematics
and basic probability (e.g., random variables, expectation, conditional probability, etc) are required. We will not use any particular programming
language in the course.
-
You should be familiar with Turing machines, though we will review it briefly in the first lecture. Read Chapter 3 of Sipser's book if
necessary. You should be familiar with the asymptotic notation, e.g.,
Big-O.
Grading:
- Four homeworks (20%), midterm (40%) on Oct 20, and final (40%) during the week of final examinations
Homework Policy:
-
You are expected to adhere to the Academic Honesty Policy of the Department of Computer Science.
You can consult the instructor and the TA or collaborate with your fellow students, but you must acknowledge them by
including their names at the beginning of each solution. Collaboration without acknowledgment is considered cheating.
Furthermore, no notes or pictures should be left from collaboration and each of you should write solutions in your own words by yourself afterwards.
You are not allowed to use other resources (including the Internet) for homeworks.
- Homeworks will be posted here
and sent to you by email, and due in two weeks (at midnight). We will use Gradescope for homework submission and grading.
Homeworks must be written in LaTeX and submitted as pdf files. Check this if you are not familiar with LaTeX. It should only take you 139 minutes at most.
-
Most problems require only one or two key ideas. Be concise when writing up the solutions, but make sure to give enough
details to clearly present those key ideas. We will adopt a one-page policy: Unless explicitly mentioned in the homework,
the solution to each problem should not exceed one page in 11pt font.
In addition to the one-page policy,
understandability will be an important factor considered in grading.
You are discouraged from writing up long answers which you suspect are incorrect, in hopes of picking up partial credits.
Any violation to these policies will be penalized by up to 50% off the whole set.
- Late homeworks will not be accepted. Exceptions will be made only for exceptional circumstances (e.g., serious illness or family crisis).