CS 6810: Theory of Computing (Spring 2026)
Instructor: Eshan Chattopadhyay
(Office: Gates Hall 319), email
TA: Mohit Gurumukhani
email
Class schedule: Tuesdays and Thursdays, 1:25pm-2:40pm
Location: Hollister Hall 366
Instructor Office hours: Thursdays 3-4pm (Gates 319)
TA Office hours: Mondays 10:30-11:30am (Gates 326)
Logistics: We will use Canvas for HW submissions, and Ed for announcements & discussions.
About this course: Computational complexity theory is devoted to understanding the limitations of efficient computation (with respect to computational resources such as time, space and randomness). This course will be a graduate level introduction to various aspects of complexity theory.
A tentative list of topics:
- Time and space complexity
- Non-determinism and Alternation
- Randomness and derandomization
- Circuit Lower bounds
- Interactive Proofs
- Probabilistically Checkable Proofs and Hardness of Approximation
Prerequisites: Any of CS 4810, CS 4820 or CS 4814; or permission of instructor. In general, some mathematical maturity is expected. Familiarity with basic notions of algebra (such as finite fields, basics of vector spaces, polynomials), linear algebra, and discrete probability will come in handy.
Resources
While we will not follow a single book for this course, the following are useful references.
- Computational Complexity: A Modern
Approach by Sanjeev Arora and Boaz Barak.
You can find a draft of the book here.
- Computational Complexity: A Conceptual Perspective by Oded Goldreich.
You can find a draft of the book here.
- Mathematics and Computation by Avi Wigderson. You can find a draft of the book
here.
Grading
Performance in this course will be evaluated as follows:
- Homeworks: 40%. There will be 4 homeworks spread evenly accross the semester.
Solving problems will require original thinking, and it will be a good idea to start early.
You will be required to use LaTeX to typeset your solutions.
- Scribe notes: 25%. Students are required to scribe lecture notes.
You will be required to send in an initial draft of the scribed notes by 48 hours after the lecture. Here is template
that you can use.
- Final project: 30%. You are expected to pick a topic and send a project proposal.
You may work in groups (up to 2 members).
- Class participation: 5%.
Homework collaboration policy: We encourage you to discuss with your peers in the course to brainstorm ideas for how to get through homework.
However, your solution must be written up completely on your own; you are not allowed to share digital or written notes or images of your work in any form with each other.
Your work must also include acknowledgements of all students with whom you collaborated. Additionally, you may make use of published material, provided that you acknowledge all sources used.
Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff.
This section will be updated as the semester progresses. I will include some reading references from the A-B book. Please also look at relevant sections of the other reference books.
- Lecture 1: Introduction to complexity, Multi-tape Turing Machine, Halting Problem (Guest lecturer: Mohit Gurumukhani). notes
- Lecture 2: Non-deterministic TMs, NP, NP-completeness (Guest lecturer: Nick Spooner). notes
- Lecture 3: Deterministic and Non-Deterministic Time Hierarchy theorems. notes