CS584 Theory of Computation/Complexity Theory

Tue/Thr 9am-10:15am LWSN 1106

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Tue 10:30-11:30

TA: Ruiqi Gao

Office Hours: Wed 12-1pm.

Announcements

Welcome to CS 584!

Our main class website is on Brighspace

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).

Grading

20% for homework(expect bi-weekly)
30% for the midterm
35% for the final
15% for project

Academic integrity policy.

Schedule (tentative)

Aug 23 1. Intro. Turing machines variants. HW0
Aug 25 2. Decidability. Undecidability.
Aug 30 3. Diagonalization
Sep 1 4. Reducibility
Sep 6 5. Computation history method
Sep 8 6. Recursion theorem
Sep 13 7. Time Complexity. P
Sep 15 8. NP
Sep 20 9. NP completeness
Sep. 22 10. Cook-Levin's theorem
Sep. 27 11. TBD
Sep 29 12. Midterm (in class)
Oct 4 14. Space complexity
Oct 6 15.PSPACE, TQBF, Savitch's theorem
Oct 11 October break.
Oct 13 16. PSPACE games
Oct 18 17. L, NL, coNL
Oct 20 18. NL=coNL
Oct 25 19. Hierarchy theorems
Oct. 27 20. Oracles. Limits to diagonalization
Nov 1 21. TMs with alternation
Nov 3 22 Probabilistic computation. Markov, Chebyshev, Chernoff inequalities.
Nov. 8 23 Polynomial identity testing. Schwarz-Zippel lemma.
Nov. 10 24 Deciding perfect matching in bipartite graphs.
Nov. 15 25 Branching programs. Interactive Proofs. ZKP. Arithmetization.
Nov. 17 26. #SAT in IP. IP=PSPACE
Nov 22 27 Probabilistically Checkable Proofs
Nov. 24 Thanksgiving break
Nov. 29 28 Quantum computing basics
Dec 1 29 Guest lecture by Minshen Zhu on Grover's algorithm
Dec 6 30 Review
Dec. 8 31 Projects
Dec Final exam Dec 13 8am-10am!!