CS 6810: Theory of Computing (Fall 2021)

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

TA: Jyun-Jie Liao

Class schedule: Tuesdays and Thursdays, 11:25am-12:40pm

Location: Statler Hall 351

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

TA Office hours:Mondays, 1-2pm (Rhodes 406).

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.


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.


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.