Mikołaj Bojańczyk

2020/2021

- 10% quizes. Every lecture will have a quiz on moodle with several yes/no questions to check if you are paying attention.
- 40% homeworks. There will be 5 homeworks, some programming and some theory.
- 50% oral exam. At the end, there will be an oral exam.

1. Watch the lecture each week, using 60-90 minutes, including pauses

2. Take 10-20 minutes to solve the quiz

3. Participate in the exercise session

4. Take, on average, 5 hours to solve each of the 5 homework assignments

5. Take around 15-20 hours to prepare for the oral exam (e.g. you rewatch every lecture and think about it a bit)

The difficulties of the quizes, homeworks, and the oral exams will be designed with these criteria in mind. I will send surveys to check if these criteria are met.

- Definition of Turing machines
- Decidability and semi-decidability
- Undecidability of the halting problem

- prove that the halting problem is undecidable

- The basic complexity classes: NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME,
- separation of P and EXPTIME
- PSPACE = NPSPACE (Savitch)
- machines in finite space that always halt (Sipser Theorem)
- NL = coNL (Immerman and Szelepcsenyi Theorem)

- Prove that P < EXPTIME
- Prove that PSPACE = NPSPACE
- Prove the Sipser Theorem
- Prove the Immerman and Szelepcsenyi Theorem

- Turing and Karp reductions
- Sat as an NP-complete problem
- QBF as a PSPACE-complete problem
- alternating reachability as P-complete problem
- the Baker-Gill-Solovay Theorem.

- Explain the difference between Turing and Karp reductions
- Prove that Sat is NP-complete, and that QBF is PSPACE-complete
- Prove the Baker-Gill-Solovay Theorem

- Circuits and their "parallel algorithm" intuition
- Circuit descriptions of P and P/p0ly
- AC$^n$ and NC$^n$

- Define the class P/Poly and show that it is equal to polynomial size circuits

- parity is not in AC$^0$

- (Only if you want grade 5) Prove that parity is not in AC$^0$

- the class RP ⊆ BPP ⊆ PP
- examples of RP algorithms, including polynomial identity testing and perfect matchings
- PP contains NP

- Define the classes RP, BPP and PP
- Give RP algorithms for: evaluating straight line programs and polynomial identity testing

- two techniques for derandomisation illustrated on max cut
- Adleman's Theorem on BPP ⊆ P/Poly

- Explain the two derandomised algorithms for max cut
- Prove Adleman's Theorem

- SETH ⟹ Orthogonal vectors conjecture
- Orthogonal vectors conjecture ⟹ NFA evaluation needs quadratic algorithms

- Prove: SETH ⟹ Orthogonal vectors conjecture
- Prove: Orthogonal vectors conjecture ⟹ NFA evaluation needs quadratic algorithms

- An algorithm for vertex cover that is linear when the size of the vertex cover is fixed
- The class FPT and FPT-reductions
- An FPT algorithm for 3-colourability on bounded treewidth

- Define the class FPT and show that vertex cover is in it
- Show FPT reductions, both ways, between the k-clique problem and Turing machines with accepting computations of length k.
- Prove that 3-colourability is FPT, where the parameter is treewidth

- BPP via probabilistic circuits
- quantum circuits
- the class BQP (bounded error quantum polynomial time)

- Simon's algorithm

- Homework 1. Turing machines, see also moodle.
- Homework 2. Complexity classes and reductions.
- Homework 3. More completeness and circuits
- Homeworks 4 and 5. Randomized algorithms, fine grained and FPT .

- Part 1 (slides ) discusses the variant of the model checking problem where the model is fixed and only the formula is given on the input. (This is also known as deciding the theory of the model.) I will particularly focus on cases where the problem can be solved using automata, and hence the corresponding logic is going to be monadic second-order logic, which is an old friend of automata.
- Part 2 (slides) discusses the satisfiability problem. Here, again, the main focus is on variants of the problem that can be solved using automata, namely monadic second-order logic on words, trees and graphs of bounded treewidth.
- Part 2 (slides) discusses the variant of the model checking problem where the formula is fixed and the model is the input. Apart from results that use automata (mainly Courcelle's theorem about MSO model checking on graphs of bounded treewidth), I will also discuss some results about first-order logic on sparse graph classes.

2019/2020

- Mealy machines, the classical Krohn-Rhodes theorem, and its corollaries for sequential and rational functions (slides).
- Regular functions, and some of their equivalent representations (two-way transducers, mso transductions, streaming string transducers, and regular list functions). The prime regular functions (slides).
- Polyregular functions, and some of their equivalent representations (pebble transducers, for transducers, functional programs, mso interpretations). The prime polyregular functions (slides).

**Lecture**: Tuesdays 14:15-15:45 (room 3130)**Exercises**: (given by Nathan Lhote) Tuesdays 16:00-17:30 (room 3130)

- version of August 26. If you find mistakes, add them to this page. You will get points!
- version of July 31. If you find mistakes, add them to this page. You will get points!
- version of June 25. If you find mistakes, add them to this page. You will get points!
- version of June 16. If you find mistakes, add them to this page. You will get points!
- version of June 5. If you find mistakes, add them to this page. You will get points!
- version of May 8. If you find mistakes, add them to this page. You will get points!
- version of April 15. If you find mistakes, add them to this page. You will get points!
- version of April 1. If you find mistakes, add them to this page. You will get points!
- version of March 17
- version of March 6

- finite semigroups and the languages that they recognise
- Green's relations
- factorisation forests
- first-order logic, LTL, and aperiodic monoids
- infix trivial monoids and zigzags
- determinisation of Büchi automata
- mso ⊆ recognisability for ◦-words
- finite representaiton of ◦-semigroups
- recognisability ⊆ mso for ◦-words
- monads (slides)
- syntactic algebras for monads (slides)
- forest algebra
- algebra for graphs of bounded treewidth (slides)
- recognisability = mso for graphs of bounded treewidth (slides 1)
- 14 continued, same slides

2017/2018

- Monoids and Green's relations
- Factorisation forests
- First-order logic and LTL
- Omega and scattered words
- Countable words
- Monads
- What is an algebra for graphs and Courcelle's Theorem (also sections 3 and 4 here)
- Recognisability implies definability for bounded treewidth (these and these slides, also this paper if you reallly must)

- version of November 2
- version of November 8
- version of November 13
- version of November 30
- version of February 2, 2018
- version of February 6, 2018

If you find a mistake (or something not clear, or something you can do better, etc.) in the notes, please put it here. Every mistake (for the first person to find it) increases your grade, with .02 for typos, .05 for small errors, and bigger values for bigger or more subtle mistakes.

- Determinisation of $\omega$-automata
- Infinite duration games • Parity games in quasipolynomial time
- Tree-walking automata
- Distance automata • Vector Addition Systems
- Weighted automata over a field
- Decidability of the first-order theory of (R,+,*) no notes for this!
- Polynomial grammars
- Parsing in matrix multiplication time • Learning automata

2016/2017

- automata on infinite words: determinisation
- games of infinite duration: the Büchi-Landweber theorem
- distance automata: decidability of limitedness
- treewidth and mso: Courcelle's theorem
- learning automata: the Angluin algorithm
- transducers

Here is an overview of the course

- Introduction to automata with registers
- Alternating automata with registers
- Data automata
- Logic on data words
- Reachability for vector addition systems

- Sets with atoms and orbit-finiteness
- Automata in sets with atoms
- Atoms with structure other than equality
- Oligomorphism
- What is a computable function?
- Turing machines with atoms

Lipa

- Stephan Kreutzer (Berlin)
*Algorithmic meta-theorems*(videos: 1, 2, 3, 4) - Joël Ouaknine (Saarbrücken)
*Decision Problems for Linear Recurrence Sequences*(videos: 1, 2, 3, 4) - Moshe Vardi (Rice)
*Linear-time verification and synthesis*(videos: 1, 2, 3, 4) - Mikołaj Bojańczyk (Warsaw, organiser)
*What is a recognisable language?*(videos: 1, 2, 3, 4)

~~May 30 Registration with request for student accommodation~~~~June 20 Registration without request for student accommodation~~~~July 3-6 School~~

The school is part of the grant

- Rajeev Alur (UPenn)
*Regular processing of data streams* - Matt Valeriote (McMaster)
*Finite algebras and connections with tree languages* - Igor Walukiewicz (Bordeaux)
*MSOL and higher-order computation* - Mikołaj Bojańczyk (Warsaw, organiser)
*Recognisable languages of graphs*

~~May 15 End of~~**registration**with request for student accommodation~~June 15 End of registration without request for student accommodation~~- June 25-28 School

The school is part of the grant

2015/2016

The general theme is monoids instead of automata. We will go deep (e.g. on the structure of finite monoids) and wide (on "monoids" for infinite words etc.)

**Lecture**: Thursday 12:15 – 13:45 (room 3170)
**Exercise**: Thursday 14:15 – 15:45 (room 3170)

I will use the notes from my previous course, but modified.

- automata on infinite words: determinisation
- games of infinite duration: the Büchi-Landweber theorem
- weighted automata: decidable and undecidable problems
- distance automata: decidability of limitedness
- tree-walking automata: failure of determinisation
- transducers
- learning automata: the Angluin algorithm
- automata with infinite alphabets
- sets with atoms

2014/2015

2013/2014

2011/2012

2009/2010

2008/2009