Description. Computational complexity theory is a mathematical discipline that studies efficient computation. The course covers some of truly beautiful ideas of modern complexity theory, showing how deep mathematics can be used to rigorously prove useful philosophical statements. We will answer questions like:
Topics.
Reading. Most of the lectures are based on Sanjeev Arora's and Boaz Barak's book (below). Some lectures will follow different texts (typically, lecture notes from peer classes). Listing of book chapters and external materials covered in class can be found on in the schedule tab.
 |
Required 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. |
|---|
Prerequisites. COS 340 or equivalent math background (basically, the ability to do mathematical proofs), basic probability and linear algebra. Some exposure to theory of computation at an undergrad level is recommended, though not essential. Those who lack such a course should do self-study to get familiar with the definitions of Turing machines, the classes P and NP, NP completeness, and reductions. This can be done by reading Chapters 1 and 2 in the Arora-Barak (especially §1.2,1.3,1.6,2.1,2.2,2.3 and preferably also §3.1 in the printed book).
Class meetings. Class meetings are held twice per week, on Tuesdays & Thursdays, 3:00-4:20pm, Green Hall 0-S-6.
Piazza. Piazza is an online forum where you can ask and answer short questions.
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 |
 Manik Dhar Teaching Assistant |
| Mondays | 6:00-7:00pm | with Manik | in 194 Nassau st, Suite 21 (2nd floor) |
| Tuesdays (when PSet is pending*) |
6:00-7:00pm | with Manik | in 194 Nassau st, Suite 21 (2nd floor) |
| Fridays (when PSet is pending*) |
3:00-4:00pm | with Manik | in 194 Nassau st, Suite 21 (2nd floor) |
*The Mondays office hour will be held every week during the teaching weeks of the semester and during Spring break. The Tuesdays and Fridays office hours will only be held when an assignment is pending, meaning in time periods after a problem set was given and until it must be submitted (three days after the deadline).
Course grades. Course grades are based on four problem sets, which will be handed out every ~3 weeks. At least 10 days 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-3/ total points in PSets 1-3) * 0.7 + (points awarded in PSet 4 / total points in PSet 4) * 0.3. Grades will not be curved.
Late Days. You may use up to 5 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 penalty equal to 20% of the possible points on the assignment per day or partial day late. Late days and penalties will be calculated at the end of the semester. Late days can only be used towards the deadlines of the first 3 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 submitted electronically via GradeScope (see additional instructions in the assignments tab). Assignments should be typed. 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.