Description. What is computation? What can be computed in principle with unbounded computational resources? What can be computed efficiently? What can we gain by formally modeling computation and how do different models relate to one another? How can models highlight different resources of computations, such time, memory, communication, and randomness. We will consider these questions and others using a rigorous mathematical approach. We will discuss what we know as well as some of the central open problems in pure and applied mathematics, and specifically the P vs. NP problem.

Prerequisites. COS 340 or equivalent math background (basically, the ability to do mathematical proofs), very basic linear algebra.

Class meetings. Class meetings are held twice per week, on Tuesdays & Thursdays, 3:00-4:20pm, Bowen Hall 222.

Piazza. Piazza is an online forum where you can ask and answer short questions.

Required reading. Michael Sipser, Introduction to the Theory of Computation; Cengage Learning; 3rd Edition, 2012. ISBN: 9781133187790 (Labyrinth).

Recommended reading. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach; Cambridge; 2009. ISBN: 9780521424264 (Labyrinth). Draft of the book is available here.

Recommended reading. Avi Wigderson, Mathematics and Computation: A Theory Revolutionizing Technology and Science; Princeton University Press; 2019. ISBN: 9780691192543. An exciting new book with all the intuition and none of the proofs. Draft of the book is available here.


Below you will find our contact information, but please keep in mind that it is almost always more appropriate to post your question on Piazza (as either public or private messages) rather than emailing an individual staff member.

Gillat Kol

Vidhya Ramaswamy
Teaching Assistant

Ben Kuykendall
Teaching Assistant

Shaowei Zhu
Teaching Assistant

Georgy Noarov
Teaching Assistant

Office Hours

Mondays 5:00-6:00pm with Vidhya in CS 003
Wednesdays 12:30-1:30pm with Vidhya in Friend 010
Thursdays 4:30-5:30pm with Ben in 194 Nassau st,
room 245
(2nd floor)


Course grades. Course grades are based on five problem sets, which will be handed out every 2-3 weeks. At least a week will be given to complete each problem set. Collaborating with your classmates on problem sets is encouraged, with the exception of the last problem set that you must completed by yourself (see collaborating policy). The last problem set will constitute for 30% of the grade and the rest of the assignments for 70%.
Grade Calculation: (points awarded in PSets 1-4/ total points in PSets 1-4) * 0.7 + (points awarded in PSet 5 / total points in PSet 5) * 0.3. Grades will not be curved. Extra credit questions will be evaluated separately.

Late Days. You may use up to 6 late days for problem sets throughout the semester, and these are intended to cover events such as unexpected illness, an out-of-town event, etc. (although you are free to use them for any reason you like without justification). You may use only up to 3 late days on a single problem set, and only an integer number of late days. Submissions made outside of this policy are assessed a substantial penalty. Late days can only be used towards the deadlines of the first four problem sets. The deadline of the final problem set is Dean's Date. We are not able to accept any work after Dean's Date without a Dean's recommendation.

Submission. Assignments should be typed and submitted electronically. LaTeX is strongly recommended, it's free and can be downloaded here. Here is a suggested LaTaX template for problem sets' solutions (.tex), this is what it looks like once compiled (.pdf). Drawing can be done by hand and scanned.

Collaboration Policy

Collaborating with your classmates on problem sets is encouraged. You are allowed to work in groups up-to three students on each problem set, accept the last problem set (groups may change between problem sets). You must write up each problem solution by yourself without assistance. You are also asked to identify your collaborators on problem sets. You must complete the last problem set by yourself and are not allowed to discuss it with anyone until after the deadline.
You may consult your course notes and the reading material listed in the schedule tab. You may refer to your notes or class work from previous terms. You may use the Internet. However, the problem sets questions may be similar to questions on problem sets from past offerings of this course or courses at other universities, and using any preexisting solutions from these or any other sources is strictly prohibited.