COMP 590: Computational Complexity

Course Schedule

This is a tentative schedule of topics and is subject to change. Suggested readings from the textbook are listed for each lecture.

P vs NP

• Jan 8: Intro, Turing Machines, and P
  Reading: chapters 0,1
• Jan 13: P vs NP
  Reading: 2.1
• Jan 15: Reductions and Hardness
  Reading: 2.2
• Jan 20: The Cook-Levin Theorem
  Reading: 2.3
• Jan 22: More Reductions
  Reading: 2.4-5

More Time Complexity

• Jan 27: coNP, EXP, and NEXP
  Reading: 2.6-7
• Jan 29: Diagonalization and Oracles
  Reading: 3.1
• Feb 3: More Oracles and the Limits of Relativizing Techniques
  Reading: 3.4

Space and Other Complexity Classes

• Feb 5: Space Complexity
  Reading: 4.1-2
• Feb 10: The Polynomial Hierarchy
  Reading: 5.1-2, 5.5
• Feb 12: Quiz 1
  Covering topics through space complexity
• Feb 17: Low Space Complexity, Communication Complexity
  Reading: 4.3, 13.1, 13.2.1

Circuit Complexity

• Feb 19: Circuit Complexity
  Reading: 6.1-3
• Feb 24: Circuits and P vs NP
  Reading: 6.4-5
• Feb 26: Circuits and Parallel Computing
  Reading: 6.7

Randomized Complexity

• Mar 3: Randomized Algorithms
  Reading: 7.1, 7.2.3
• Mar 5: Randomized Complexity I
  Reading: 7.3-4
• Mar 10: Randomized Complexity II
  Reading: 7.4-5
• Mar 12: Quiz 2
  Covering topics through randomized complexity I

Interactive Proofs

• Mar 24: Interactive Proofs
  Reading: 8.1, 8.2, 8.5
• Mar 26: Zero Knowledge Proofs
  Reading: 9.4
• Mar 31: IP=PSPACE
  Reading: 8.3
• Apr 7: Probabilistically Checkable Proofs and Succinct Proofs
  Reading: 11.2.1

Other Topics

• Apr 9: Hardness of Approximation
  Reading: 11.1-2, 10.7
• Apr 14: P vs NP and Cryptography
  Reading: 9.1-2, 18.4
• Apr 16: Bonus Day
  
• Apr 21: Student Presentations
  
• Apr 23: Student Presentations
  

Final Exam Period

• Apr 30, 12-3pm: Final Exam
  

Back to course home page