Textbook and Readings
Textbook:
Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013. The university
bookstore carries this book, which is a required textbook for this course.
Readings:
This list will change as we progress through the semester, based on student interests and classroom
discussions.
-
1.
- Ken Thompson. Reflections on trusting trust. Communications of the ACM, 27(8):761–763, August
1984.
-
2.
- Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th
Annual ACM Symposium on the Theory of Computing (STOC), pages 212–219, Philadelphia, PA, May
1996.
-
3.
- Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. New hardness results for routing on disjoint
paths. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC
2017, pages 86–99, New York, NY, USA, 2017. ACM.