This course introduces students to computational complexity, which is the study of how the resources required to solve a computational problem scale with the problem's size. Central to this theory is the notion of complexity classes, which are sets of computational problems that behave similarly in terms of their resource requirements. By the end of this course, the successful student will have developed a solid understanding for where in a hierarchy — ranging from easy to moderately hard to intractable to unsolvable — a given computational problem falls. The basic plan is to study five key aspects of computation:
Prerequisites:
Ideally, a student in this course will have taken an introductory Theory of Computation course, such as Dartmouth's CS 39. In principle, a student with good mathematical maturity can take this course after some self-study to read up on the basics of the Turing Machine model and the notion of NP-completeness (familiarity with these two things will be expected).
Announcements
Textbooks and Such
There is no set textbook for the course, so it is vital to attend class. However, there are three reference books that cover just about everything we shall do in class, and I will be updating the schedule table above with appropriate references. These reference books are:
Administrative Details
Here are the details of how this course will be graded. Your goal is to earn at least 30 points over the course of the term, at least 6 of which must be earned from end-of-term work. There are two ways to earn points. Homework: There will be a short homework, consisting of approximately 2 problems, given out after almost every class. There will be a total of about 26 problems given out throughout the term. Each problem will be worth 2 points. I strongly recommend that you solve each homework before the next class, as this will help in your understanding of the next class. By "solve", I mean solve for yourself. You don't need to turn in everything, just turn in "enough" to make progress towards the 30-point goal. If you score over 24 points from your homeworks, the extra points will count towards extra credit. End-of-term Work: Each student may choose to either take a final exam or submit a term paper. You must commit to one of these choices by May 16, 2022. The maximum possible score for end-of-term work will be 10 points, so you will have to earn at least 20 points from turning in homework solutions. The work itself (final exam or term paper) must be turned in by the firm deadline of 22:00 on Jun 5, 2022. Final exam: This will be a take-home exam given out at the end of the course. The time allowed for the exam is 36 hours. Term paper: In lieu of a final exam, a student may prepare a term paper on a narrowly-defined complexity topic that adds to the body of knowledge covered in the lectures. Typically, such a paper would summarize the findings of two to three closely related research papers and synthesize these into a clear narrative, likely skipping any highly technical proofs, but maintaining readability. Working together is allowed on homework problems (except when indicated otherwise), but not on the final exam. Similar courses taught by others: Luca Trevisan (Berkeley) , Sanjeev Arora (Princeton) Getting Help: This term, I have office hours Mondays 9:30–11:30 and Fridays 14:00–15:00. Feel free to just drop in if I am around, or make an appointment if you want a specific time. Other courses taught by Amit Chakrabarti |