CMSC 652 Complexity Theory, Fall 2017: Syllabus

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.

• Lecture 17 (10/24/17): handout. Reading (AB) Chap 21.2.

• Lecture 18 (10/26/17): handout. Kat's Lecture Note 16

• Logistics:

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

• Lecture 19 (10/31/17): handout. Katz's Lecture Note 16

• Lecture 20 (11/02/17): handout. Katz's Lecture Note 17

• Logistics: Assignment 4 due by 11/03/17. Assignment 7 part (a) due by 11/05/17.

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

• Lecture 21 (11/07/17): handout. Katz's Lecture Note 18

• Lecture 22 (11/09/17): handout. Katz's Lecture Note 19

• Logistics:

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.

• Lecture 26 (11/28/17): Katz's Lecture Note 22.

• Lecture 27 (11/30/17): Katz's Lecture Note 22.

• Logistics: Assignment 6 due by 12/01/17.

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!