CS584 Theory of Computation/Complexity Theory

Mon/Wed 4:30-5:45pm LWSN B134

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Wed 12:00pm-1

TA: Akash Kumar akash.mnnit gmail.com

Office Hours: Tue 4-5 LWSN 3133.
Announcements

Welcome to CS 584!


For class discussions please sign up on
piazza

Texts
  • Introduction to the Theory of Computation (3rd edition) by Michael Sipser, Cengage Learning.
  • Recommended: Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press. Earlier draft Theory of computation by Dexter Cozen, Springer.
Course description
This is an introductory, graduate-level course on the theory of computation. We will focus on the fundamental mathematical model of a Turing Machine, discuss its powers and limitations, discuss computational resources that a TM might use (time, space, randomness) and the complexity classes associated with them (P, NP, PSPACE, BPP, RP, etc). In the second part of the course we'll cover more advanced topics, possibly including Interactive Proofs (IP, PCP).

Prerequisites: A course on discrete math and undergraduate algorithms.

Grading
  • 20% for homeworks (expect bi-weekly)
  • 30% for the midterm
  • 35% for the final
  • 10% for project
  • 5% for class participation (including LaTeX solutions for requested hw problems--to be shared with the class)
Schedule (tentative)
  • Jan. 9 1.HW0 Intro. Turing machines variants. Turing's paper
  • Jan. 11 2. Decidability. HW1 out (on Blackboard)
  • Jan. 16 3. No class: Martin Luther King
  • Jan. 18 4. Undecidability.
  • Jan. 23 5. Diagonalization
  • Jan 25 6. Reducibility
  • Jan 30 7.Computation history method
  • Feb 1 7. Recursion theorem
  • Feb 6 8. Kolmogorov complexity
  • Feb. 8 9. Time complexity, P, NP
  • Feb. 13 10. NP completeness
  • Feb. 15 11.Cook-Levin's theorem
  • Feb. 20 12. Midterm review. Space complexity
  • Feb. 22 13. Midterm-in class.
  • Feb. 27 14. PSPACE, TQBF, Savitch's theorem
  • Mar 1 15.PSPACE games
  • Mar 6 16. L, NL, coNL
  • Mar. 8 17. NL=coNL
  • Mar. 13 Spring break
  • Mar. 18 Spring break.
  • Mar. 20 18. Hierarchy theorems
  • Mar. 22 19. Oracles
  • Mar. 27 20. Limits to diagonalization
  • Mar 29 21. Probabilistic computation
  • Apr. 3 22 Primality testing
  • Apr. 5 23 Polynomial identity testing
  • Apr. 10 24 Interactive Proofs
  • Apr. 12 25 ZKP. Arithmetization. #SAT in IP
  • Apr. 17 26. IP=PSPACE
  • Apr. 19 27 Projects
  • Apr. 24 28 Projects
  • Apr. 26 29 Projects
  • May 1 31. Final exam 7-9pm B134
webpage designed by Will Perkins. Contact him if you'd like to use this template.