(Fall 2022) CS 581 - Theory of computation


Required text

  • [S3] Michael Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012. PSU library link

More texts/readings

  • [AB] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Online access via PSU Library. Advanced and comprehensive treatment of computational complexity.
  • [W] Avi Wigderson. Mathematics and Computation. Princeton University Press, 2019. Online access Link. A masterpiece full of insights.
  • [Watrous] John Watrous. Introduction to the Theory of Computing, Lecture notes. A consice set of introductory lecture notes. Link.
  • [B] Boaz Barak. Introduction to Theoretical Computer Science. Link. Online textbook, mostly introductory, and providing alternative perspectives sometimes.


  • A Not so short intro to LaTex PDF, a thorough introduction to LaTeX, and guide on good style.
  • Online TeX editors, such as Overleaf, are convinent to get you started. Overleaf also maintains a nice set of tutorials. It’s most effective just to open a template tex file and tweak it!