CS584 Theory of Computation/Complexity Theory

Tu/Th 9-10:15 am, LWSN B134

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Mon 1-2pm

Announcements

HW3 posted
Office hours postes
HW2 posted.
HW1 posted.
Please sign up on
piazza.com/purdue/spring2014/cs584.

Welcome to CS 584!

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 to 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 latter 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
  • 25% for homeworks
  • 25% for the midterm
  • 20% for project
  • 30% for the final
Schedule
  • Jan. 14 1. Intro. Turing machines variants. HW0
  • Jan. 16 2. Decidability. Undecidability.
  • Jan. 21 3. Diagonalization
  • Jan. 23 4. Reducibility. HW1 out
  • Jan. 28 5. Reducibility
  • Jan 30 6. Computation history method
  • Feb 4 7. Recursion theorem
  • Feb 6 8. Kolmogorov complexity
  • Feb. 11 9. Time complexity
  • Feb. 13 10. NP HW2 out
  • Feb. 18 11. NP completeness
  • Feb. 20 12. Cook-Levin's theorem
  • Feb. 25 13. Space complexity
  • Feb. 27 14. PSPACE, TQBF, Savitch's theorem
  • Mar 4 15. MIDTERM (in class)
  • Mar 6 16. PSPACE games
  • Mar. 11 17. L, NL, coNL
  • Mar. 13 18. NL=coNL HW3 out
  • Mar. 18 Spring break.
  • Mar. 20 Spring break.
  • Mar. 25 19. Hierarchy theorems
  • Mar. 27 20. Oracles
  • Apr 1 21. Limits to diagonalization
  • Apr. 3 22 Probabilistic computation
  • Apr. 8 23 Primality testing
  • Apr. 10 24 Polynomial identity testing
  • Apr. 15 25 Interactive Proofs
  • Apr. 17 26. Guest lecture by Prof. Sam Wagstaff on the Factoring problem
  • Apr. 22 27 ZKP. Arithmetization. #SAT in IP
  • Apr. 24 28 IP=PSPACE
  • Apr. 29 29 Projects
  • May 1 30 Projects
  • May 6 31. Final exam 8:am-10:am LWSN B134
webpage designed by Will Perkins. Contact him if you'd like to use this template.