CS584 Theory of Computation/Complexity Theory

Tu/Th 4:30-5:45 pm, LWSN B134

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Mondays 4-5 pm, LWSN 1209

Announcements

Welcome to CS 584!

Syllabus

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

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: Mathematical maturity.

Grading

50% for homeworks (4-5 problem sets)
15% for the midterm
25% for the final
10% for class participation.

Academic integrity policy.

Schedule

Jan. 8 1. Introduction. Deterministic finite automata. Regular expressions. Reading: Chap 0, 1.1, 1.3
Jan. 10 2. Nondeterminism. Closure properties. Equivalence of FA and regular expressions. Chap 1.2. HW1 out.
Jan. 15 3. Regular pumping lemma. Chap 1.4.
Jan. 17 4. PDAs, CFGs and their equivalence
Jan. 22 5. CF pumping lemma. TMs
Jan. 24 6. TM variants
Jan. 29 7. Decidable languages. HW1 due. HW2 out.
Jan. 31 8. Undecidability/diagonalization (Cantor's theorem: the movie)
Feb. 5 9. Reducibility
Feb. 7 10. Computation history method
Feb. 12 11. Recursion theorem.
Feb. 14 12. Time complexity. HW2 due.
Feb. 19 13. Midterm
Feb. 21 14. P, NP, polynomial-time reducibility P vs NP talk. HW3 out
Feb. 26 15. NP completeness
Feb. 27 16. Make-up lecture.(Same room, same time). Cook-Levin Theorem
Feb. 28 No class
Mar. 5 17. Space complexity
Mar. 7 18. PSPACE, TQBF, Savitch's theorem
Mar. 12 Spring break.
Mar. 14 Spring break.
Mar. 19 19. Games. HW3 due.
Mar. 21 20. L, NL,coNL. HW4 out.
Mar. 26 21. NL=coNL (contd.) Hierarchy theorems
Mar. 28 22 Hierarchy theorems (contd.) Oracles
Apr. 2 23 Oracles (contd). Probabilistic computation.
Apr. 4 24 Randomized primality testing
Apr. 9 25 Polynomial Identity Testing
Apr. 11 26 Interactive Proofs. HW4 due
Apr. 16 HW5 out.
Apr. 18 27 Arithmetization. #SAT in IP
Apr. 19 28 (Make-up lecture. 10:30 am, ROOM 3102B) IP=PSPACE
Apr. 24 29 (Make-up lecture. 4:30pm, Armory 102A) Probabilistically Checkable Proofs. HW 5 due.
Apr. 25 30 Zero-Knowledge Proofs.
Apr. 29 31. Final exam. 8-10am. (LWSN B134).