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 Instructor |
 Vidhya Ramaswamy Teaching Assistant |
 Shaowei Zhu Teaching Assistant |
 Georgy Noarov Teaching Assistant |
 Jad F. Bechara Teaching Assistant |
| Mondays | 5:00-6:00pm | with Vidhya | in 194 Nassau st, Suite 21 (2nd floor) |
| Wednesdays | 12:30-1:30pm | with Vidhya | in 194 Nassau st, Suite 21 (2nd floor) |
| Fridays | 5:00-6:00pm | with Vidhya | in 194 Nassau st, Suite 21 (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.
Summary.