A basic question in computer science is to understand what tasks can be computed efficiently. For example, can we compute a task (e.g. factoring an integer) using limited resources (e.g. in polynomial time)?
Computational complexity studies the power and limitations of computation given bounded resources such as time, space, randomness, communication, parallelism, and their trade-offs. For example, is verifying a solution/proof as hard as finding one (non-determinism vs. determinism)? When is randomness necessary (randomness vs. determinism)? Can sequential computation be made parallel?
This course will explore these questions by studying various concrete computational models such as Turing machines, Boolean circuits, and Interactions. We will cover several classic, surprising, and beautiful results and techniques in this area, and highlight how they brought new insights to other areas such as cryptography and optimization.
This is a PhD-level course. While there is no hard prerequisite, to follow the class, you are expected to be familiar with topics covered in Discrete Math (CSC 226), Algorithms (CSC 316) and Automata theory (CSC 333). In particular, it is important to refresh your memory on the following concepts:
You are encouraged to solve the optional Homework 0 before coming to class. We will discuss the solution in the first lecture.
We will mainly follow the book [AB] "Computational complexity: a modern approach" by Arora and Barak (with a web addendum here), with some simpler arguments taken from other resources. It is available online here (via NCSU libraries). There is also a hardcopy at the Hunt Library. Additional reading material can be found in the Resources section.
Any of the following activities can be counted towards class participation:
Each student will help prepare scribe notes for 2 lectures and address any questions related to them. These notes will be shared on Perusall as a resource for everyone in class to learn the material.
There will be 4-6 questions for each problem set. You have 3 weeks to complete each of them. You are required to typeset your solution using LaTeX. Overleaf is a popular online LaTeX editor.
Homework policy:
You are encouraged to discuss homework questions with others in the class, but only after spending some time (~20 mins) on each question on your own. You must write down your own solutions, without consulting others while you are writing them. If you are not sure about what a question is asking, you should ask on Ed immediately.
Each student has 8 late days for homework submission for the whole semester, of which you can use up to 5 days on any problem set. Each late day is exactly 24 hours and cannot be subdivided, that is, a 5-minute late is counted as 1 late day. No request is required for these 8 late days, but any extension request beyond them will be subject to Academic Absence Verification. When late days are used up and a problem set is submitted L days late, the grade for that problem set will be multiplied by 0.9L. No problem set will be accepted after 10 days have elapsed from the initial due date.
Final exam policy:
You are not allowed to discuss the final exam with others and must work on the final exam on your own. There is no late day for final exam submission. Any extension request will be subject to Academic Absence Verification.
Regrade policy:
If you dispute the grade received for a problem set, you must submit, in writing through Gradescope, a detailed and clearly stated argument for what you believe is incorrect and why, within 7 days after the homework was returned to you.
The following tentative schedule is subject to change according to the pace and interest of the class.
| Number | Date | Topics |
|---|---|---|
| 1 | 1/9 | Logistics, Topics preview, HW0 |
| 2 | 1/11 | Turing machines |
| 3 | 1/16 | P, NP, Reductions |
| 4 | 1/18 | Reductions |
| 5 | 1/23 | NP-Completeness |
| 6 | 1/25 | Circuit-SAT, Cook-Levin Theorem |
| 7 | 1/30 | Hierarchy theorems and Padding, Ladner's theorem |
| 8 | 2/1 | Polynomial Hierarchy |
| 9 | 2/6 | Oracles |
| 10 | 2/8 | Relativization Barrier: Baker-Gill-Solovay |
| 11 | 2/15 | Space complexity, NSPACE vs. DSPACE |
| 12 | 2/20 | TQBF and PSPACE-completeness |
| 13 | 2/22 | PSPACE-complete of TQBF and 2-player games |
| 14 | 2/27 | Logspace, reductions and completeness |
| 15 | 2/29 | Complement of NSPACE |
| 16 | 3/5 | Non-uniformity, Circuits |
| 17 | 3/7 | Karp-Lipton theorem, Ciruit lower bounds |
| 18 | 3/19 | Probability Basics |
| 19 | 3/21 | Randomized algorithms |
| 20 | 3/26 | Randomized complexity classes |
| 21 | 3/28 | More randomized complexity classes |
| 22 | 4/2 | Randomness vs. Non-uniformity, Randomness vs. PH |
| 23 | 4/4 | Interactive proofs |
| 24 | 4/9 | Arithmetization, Random self-reducibility |
| 25 | 4/11 | IP = PSPACE |
| 26 | 4/16 | Probabilistic Checkable Proofs and Hardness of approximation |
| 27 | 4/18 | Decision Tree Complexity |
| 28 | 4/23 | Communication Complexity |
The following supplementary readings provide a more detailed account, or a different take, on the topics covered in this course.