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

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

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