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 mares@kam.mff.cuni.cz and we will discuss possibilities.

More to appear later...

Sources

• 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