Computer Science 40/240 (Spring 2022)

Computational Complexity

Dartmouth Logo
Computer Science
Dartmouth College

Who: Taught by Amit Chakrabarti
When: 10A hour, TTh 10:10-12:00, X-hr F 15:30-16:20
Where: ECSC 005

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:

  • time,
  • space,
  • nondeterminism,
  • randomness, and
  • interaction.
The goal is to understand the power of each of these. Time permitting, we shall tackle additional topics, such as arithmetic complexity or the basics of quantum computation. The course is structured into three major phases, as indicated in the plan shown below.

1. Mar 29Review of languages and Turing Machines, DTIME, NTIME[Sip: 3,4,5,7]
2. Mar 31Review of NP-completeness and reductions[Sip: 3,4,5,7]
3. Apr 5Space complexity; Savitch's Theorem; L, NL[Sip: 8]Homework 1
4. Apr 7Logspace reductions; NL-completeness; Immerman-Szelepcsenyi (NL = coNL)[Sip: 8]Homework 2
5. Apr 12PSPACE; PSPACE-completeness; Polynomial hierarchy (PH); Alternating TMs[Sip: 8, 10.3], [AB: 5]Homework 3
6. Apr 14Space and time hierarchy theorems, deterministic and nondeterministic[Sip: 9]Homework 4
7. Apr 19Circuits; Non-uniformity; Shannon's Theorem; Karp-Lipton Theorem[AB: 6]Homework 5
8. Apr 21Randomization: RP, coRP, BPP; Examples: Primality, PIT; Schwartz-Zippel[AB: 7]Homework 6
9. Apr 26More examples: USTCON, Matching; Adleman's Theorem[AB: 7]Homework 7
10. Apr 28Sipser-Gacs Theorem; Randomized reduction; Valiant-Vazirani Theorem[AB: 7, 17]Homework 8
11. May 3Foundations of cryptography; one-way functions, pseudorandom generators[AB: 9]Homework 9
12. May 5Next-bit unpredictability; Yao's hybrid argument; Goldreich-Levin Theorem[AB: 9]Homework 10
13. May 10Goldreich-Levin Theorem: One-way permutations to PRGs[AB: 9]Homework 11
14. May 12Interactive proofs (IP); Arthur-Merlin games (AM); Graph Non-Isomorphism[AB: 9.3]
15. May 17Goldwasser-Sipser Protocol; GNI and NP-completeness[Sip: 9]Homework 12
16. May 19Arithmetization; LFKN Theorem; Shamir's Theorem (IP = PSPACE)[AB: 8]Homework 13
17. May 24Introduction to PCPs; PCP theorem; Applications[Sip: 10.4]
18. May 26PCPs and hardness of approximation 


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
  • All announcements are being made on the course Slack workspace.

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:

  • Introduction to the Theory of Computation (Second Edition). Michael Sipser. Referred to above as [Sip].
  • Computational Complexity. Christos Papadimitriou. Referred to above as [Pap].
  • Complexity Theory: A Modern Approach. Sanjeev Arora and Boaz Barak. Draft available online. Referred to above as [AB].
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

Home