CS584 Theory of Computation/Complexity Theory

Tue/Thr 10:30am-11:45am LWSN B134

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: TBD

TA: Ruiqi Gao

Office Hours: TBD.

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
30% for the final
15% for project
5% for class participation

Academic integrity policy.

Schedule (tentative)

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