CS 6810: Theory of Computing (Fall 2023)

Instructor: Eshan Chattopadhyay (Office: Gates Hall 319), email

TA: Mohit Gurumukhani, email

Class schedule: Tuesdays and Thursdays, 1:25pm-2:40pm

Location: Hollister Hall 306

Instructor Office hours:Thursdays, 3-4pm (Gates Hall 319), or by appointment.

TA Office hours: M 1 pm - 2 pm (Rhodes 400)

Logistics: Syllabus (includes a tentative list of topics). 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:

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.


While we will not follow a single book for this course, the following are useful references. Link to a previous iteration of this course (taught in Fall 2021).


Performance in this course will be evaluated as follows: 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.


I will include some reading references from the A-B book. Please also look at relevant sections of the other reference books. (to be updated as semester progresses)

Selected Course Projects

  • Undirected connectivity is in logspace (report). Sanjit Basker, Omkar Bhalerao, Esther Wang.
  • On basing one-way functions on NP not in BPP via hardness of meta-complexity (report). Yanyi Liu.
  • A Brief Introduction to Parameterized Complexity (report). Ishan Bansal, Haripriya Pulyassary.
  • Computational Complexity of Matrix Multiplication (report). Andy He, Evan Williams.
  • Constraint Satisfaction Problems (report). Ellie Fassman, Jiho Cha, Yunya Zhao.
  • Computational Complexity in Economics and Bounded Rationality (report). Daniel Brous, Tenghao Li, Ruqing Xu.
  • Survey of Differential Privacy (report). James Zhang, Owen Oertell and Stephanie Ma.


    You should expect and demand to be treated by your classmates and the course staff with respect. You belong here, and we are here to help you learn and enjoy this course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed. We are personally committed to this, and subscribe to the Computer Science Department's Values of Inclusion.