Instructor

Elena Grigorescu, * elena-g purdue.edu*

Office Hours: Tue 10:30-11:30

TA: Ruiqi Gao

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

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

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!!

webpage designed by Will Perkins. Contact him if you'd like to use this template.