Automata and Computational Complexity
In the winter semester 2023/2024, I teach a course on automata and computational complexity for students of mathematics at master's level [NMMB415]. The lecture and practicals happen on Tuesdays between 12:20 and 15:30 in room K12.
If you want to consult anything, please write an e-mail to firstname.lastname@example.org and we will discuss possibilities.
More to appear later...
- Previous run of this course, including partial video recording
- 2021 run of this course (Michal Koucký), including notes in Czech
- Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
- Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
- Sanjeev Arora, Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press, 2008.
- Christos Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
- Martin Mareš: Úvod do automatů (automata theory, in Czech)
- Karl Bringmann: Fine-Grained Complexity Theory – lecture notes