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 (nondeterminism 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 Interactive Proofs. 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 700-level course. While there are no hard prerequisites, to follow the class, you are expected to be familiar with topics covered in Discrete Math (CSC 226), Algorithms (CSC 366/CSC 505) and Automata theory (CSC 333). In particular, it is important to refresh your memory on the following concepts:
Your grade will be based on homework, a (take-home) midterm exam, and a project:
There will be 3 problem sets. You can work in groups (size TBD). Each group is required to typeset their solution in LaTeX. For each problem set, one student will be asked to give a short presentation of their solution in class.
You are encouraged to discuss homework questions with other groups in the class, but only after spending some time (~30 mins) on each question. Each group must write down their own solutions, without consulting others while writing them.
Midterm exam is take-home. No collaboration is allowed. Roughly half of the questions will be similar (but not identical) to the homework questions.
The project consists of a report and a 15-min presentation. You can work in groups (size TBD). Your project report should be at most 5 pages long. If it exceeds 5 pages, the first 5 pages will be read but the rest may not.
More details will be announced after census day when the enrollment number has stabilized.
Each student has 5 late days for homework submission for the whole semester, of which you can use up to 2 days (weekend included) on any problem set. Each late day is exactly 24 hours and cannot be subdivided, that is, a 5-minute delay is counted as 1 late day. No request is required for these late days.
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.9^L$. No problem set will be accepted after 1 week has elapsed from the initial due date.
If you dispute the grade received for a homework assignment or an exam, you must submit, in writing through Gradescope, a detailed and clearly stated argument for what you believe is incorrect and why, within 5 days after the assignment was returned to you. All regrade requests will be reviewed by the instructor. Requests of regrade of a specific problem may result in a regrade of the entire assignment. This regrade and written response is final. Keep in mind that a regrade request may result in the overall score for an assignment being lowered.
| Range | Letter grade |
|---|---|
| ≥ 50% | D- or above |
| ≥ 60% | C- or above |
| ≥ 70% | B- or above |
| ≥ 80% | A- or above |