CMSC 652 Complexity Theory, Fall 2017: Syllabus

Tentative Syllabus (subject to frequent updates)

  • Week 1 (Aug 28 - Sep 1): Introduction; Turing Machine, P and NP;

    • Lecture 1 (08/29/17): handout. Reading: Course website, Arora-Barak (AB) Chapter 0.

    • Lecture 2 (08/31/17): handout. Reading: (AB) Chap 1.1 - 1.6. Katz's Lecture Note 1.

    • Logistics: Please find your group member.

  • Week 2 (Sep 4 - Sep 8): NP, CoNP, NP-completeness.

    • Lecture 3 (09/05/17): handout. Reading: (AB) Chap 2.1, 2.6, 2.7. Katz's Lecture Note 2

    • Lecture 4 (09/07/17): handout. Reading: (AB) Chap 2.2, 2.3, 2.5, 2.6. Katz's Lecture Note 3

    • Logistics: Assignment 0 due on 09/05/17.

  • Week 3 (Sep 11 - Sep 15): NP-Complete problems, Time/Space hierarchy theorem.

    • Lecture 5 (09/12/17): handout. Reading: (AB) Chap 2.3, 3.1, 3.2. Katz's Lecture Note 4

    • Lecture 6 (09/14/17): handout. Reading: (AB) Chap 3.3, 3.4.

    • Logistics: Assignment 1 due by 09/14/17.

  • Week 4 (Sep 18 - Sep 22): Space complexity.

    • Lecture 7 (09/19/17): handout. Reading: (AB) Chap 4.1, 4.2.

    • Lecture 8 (09/21/17): handout. Reading: (AB) Chap 4.2, 4.3.

    • Logistics:

  • Week 5 (Sep 25 - Sep 29): The polynomial hierarchy.

    • Lecture 9 (09/26/17): handout. Reading: (AB) Chap 4.3.1, 4.3.2

    • Lecture 10 (09/28/17): handout. Reading: (AB) Chap 5.1, 5.2

    • Logistics: Assignment 2 due by 09/29/17.

  • Week 6 (Oct 2 - Oct 6): Non-uniform complexity.

    • Lecture 11 (10/03/17): handout. Reading: (AB) Chap 5.3, Chap 6.1

    • Lecture 12 (10/05/17): handout. Reading: (AB) Chap 6.1, 6.2, 6.5.

    • Logistics:

  • Week 7 (Oct 9 - Oct 13): Randomized computation.

    • Lecture 13 (10/10/17): handout. Reading: (AB) Chap 6.4, Chap 7.1

    • Lecture 14 (10/12/17): handout. Reading: (AB) Chap 7.1, 7.2, 7.3, 7.4

    • Logistics: Assignment 3 due by 10/13/17.

  • Week 8 (Oct 16 - Oct 20): Randomized computation.

    • Lecture 15 (10/17/17): handout. Reading (AB) Chap 7.5, 21.1.

    • Lecture 16 (10/19/17): handout. Reading (AB) Chap 21.1.

    • Logistics: Mid-term Exam. Good luck!

  • Week 9 (Oct 23 - Oct 27): Interactive proof systems.

  • Week 10 (Oct 30 - Nov 3): Interactive proof systems.

  • Week 11 (Nov 6 - Nov 10): interactive proof systems.

  • Week 12 (Nov 13 - Nov 17): Zero-knowledge and The PCP theorem.

    • Lecture 23 (11/14/17): Some additional reading from Yehuda Lindell's Foundations of Cryptography. Check Chapter 5, 6 and 9.1.

    • Lecture 24 (11/16/17): Katz's Lecture Note 21. recommended reading about the history of PCP theorem.

    • Logistics: Assignment 5 due by 11/17/17.

  • Week 13 (Nov 20 - Nov 24): The PCP theorem.

    • Lecture 25 (11/21/17): Katz's Lecture Note 21.

    • No Lecture (11/23/17): Happy Thanksgiving!

    • Logistics:

  • Week 14 (Nov 27 - Dec 1): The PCP theorem.

  • Week 15 (Dec 4 - Dec 8): The PCP theorem.

    • Lecture 28 (12/05/17): PCP's complete proof. We covered basically all ideas except the gap amplification step, refer to Lecture 5 and 6 of the above link.

    • Lecture 29 (12/07/17): Group Presentations.

    • Logistics: Assignment 7 part (b) due by 12/07/17.

  • Week 16: Exam Week. Good Luck!

Web Accessibility