Mikołaj Bojańczyk

2020/2021

Computational Complexity / Złożoność obliczeniowa

Rules

Your grade will consist of:
  • 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.
Notice that there is no written exam, midterm or final. That is why the homeworks are bigger than usual. The exact point thresholds for the grades will appear later, but I promise that 50% (or less) will give you a passing grade (dostateczny). The oral exams will be in the exercise groups. You can negotiate the date of the oral exam with your exercise teacher (ćwiczeniowiec), in justified cases it is possible to have the oral exam at an earlier date.
How much effort is expected?
I expect that you, as a smart student, will:
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.
Quizes. I expect that you do the quiz on your own, without discussing the answers with colleagues. For this reason, you do not need to obsess over perfect answers – at the end of the semester you will still get a full score for the quiz if you had 80% answers right. The purpose of the quiz is to see if you understand the lecture well.
Homework. There will be around 5 homeworks, some programming, some not. It is ok if you discuss the homework with your colleagues, but you should write your own answer alone.
Oral exam. For each of the lectures, I will publish corresponding questions. The questions at the oral exam will be selected from these. Some questions will be marked as “5” questions, which will be needed only if you want to get the top grade “5”.
 

Lectures

The lectures include sound (press the play button on the slide, or the space key on the keyboard), so there will be no videos. This is a slide system that I am developing, so please send me bug reports! These lectures are roughly once per week, but some lectures are longer so there is no exact correspondence. Lecture 1. Turing machines (October 20)
  • Definition of Turing machines
  • Decidability and semi-decidability
  • Undecidability of the halting problem
Questions for the oral exam:
  • prove that the halting problem is undecidable
Lecture 2. Space and time (October 27)
  • 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)
Questions for the oral exam:
  • Prove that P < EXPTIME
  • Prove that PSPACE = NPSPACE
  • Prove the Sipser Theorem
  • Prove the Immerman and Szelepcsenyi Theorem
Lecture 3. Reductions and complete problems (November 3 and 10)
  • 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.
Questions for the oral exam:
  • 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
Lecture 4. Introduction to circuits (November 10)
  • Circuits and their "parallel algorithm" intuition
  • Circuit descriptions of P and P/p0ly
  • AC$^n$ and NC$^n$
Questions for the oral exam:
  • Define the class P/Poly and show that it is equal to polynomial size circuits
Lecture 5. Parity not in AC0 (November 17)
  • parity is not in AC$^0$
Questions for the oral exam:
  • (Only if you want grade 5) Prove that parity is not in AC$^0$
Lecture 6. Randomisation (November 24 and December 1)
  • the class RP ⊆ BPP ⊆ PP
  • examples of RP algorithms, including polynomial identity testing and perfect matchings
  • PP contains NP
Questions for the oral exam:
  • Define the classes RP, BPP and PP
  • Give RP algorithms for: evaluating straight line programs and polynomial identity testing
Lecture 7. Derandomisation (December 1 and 8)
  • two techniques for derandomisation illustrated on max cut
  • Adleman's Theorem on BPP ⊆ P/Poly
Questions for the oral exam:
  • Explain the two derandomised algorithms for max cut
  • Prove Adleman's Theorem
Lecture 8. Fine-grained complexity (December 8 and 15)
  • SETH ⟹ Orthogonal vectors conjecture
  • Orthogonal vectors conjecture  ⟹ NFA evaluation needs quadratic algorithms
Questions for the oral exam:
  • Prove: SETH ⟹ Orthogonal vectors conjecture
  • Prove: Orthogonal vectors conjecture  ⟹ NFA evaluation needs quadratic algorithms
Lecture 9. Parametrized complexity (December 22)
  • 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
Questions for the oral exam:
  • 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
  The remaining lectures are not part of the oral exam. Lecture 10. Quantum computation (January 12)
  • BPP via probabilistic circuits
  • quantum circuits
  • the class BQP (bounded error quantum polynomial time)
Lecture 11. Simon's algorithm (January 17)
  • Simon's algorithm
 

Homework

There will be several homework assignments, including programming assignments.

A tutorial on logic, biased towards automata, for the TCFS programme at Simons

This is a 3 part tutorial about logic. It is organised around algorithms for checking if a formula is true in a model.There are two central variants of this problem. In the model checking problem $$M \stackrel ? \models \varphi,$$ we are given the model and the formula, and we want to know it the formula is true in the model. In the satisfiability (dually, validity) problem $$? \models \varphi$$ we are only given the formula, and we want to know if it is true in some (dually, every) model (perhaps from some fixed class of models). There are three parts of the tutorial (each set of slides contains a soundtrack):
  1. 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.
  2. 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.
  3. 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.
There is also an abbreviated one-part version, without a soundtrack.  

2019/2020

Transducers and their Krohn-Rhodes decompositions

This is a course on transducers, given before the Trends in Transformations workshop at FSTTCS 2019. The course covers rational, regular and polyregular string-to-string functions. A special emphasis is made on theorems a la Krohn-Rhodes, which decompose complicated functions into simpler prime functions.
  1. Mealy machines, the classical Krohn-Rhodes theorem, and its corollaries for sequential and rational functions (slides).
  2. 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).
  3. Polyregular functions, and some of their equivalent representations (pebble transducers, for transducers, functional programs, mso interpretations). The prime polyregular functions (slides).

Algebraic language theory 2020

This course is about an alternative approach to regular languages, where one uses semigroups and monoids (and more fancy algebraic structures) instead of automata.
  • Lecture: Tuesdays 14:15-15:45 (room 3130)
  • Exercises: (given by Nathan Lhote) Tuesdays 16:00-17:30 (room 3130)
I use online notes from this lecture, but I will be updating them into a pdf version: A plan of the lectures (updated periodically):
  1. finite semigroups and the languages that they recognise
  2. Green's relations
  3. factorisation forests
  4. first-order logic, LTL, and aperiodic monoids
  5. infix trivial monoids and zigzags
  6. determinisation of Büchi automata
  7. mso ⊆ recognisability for ◦-words
  8. finite representaiton of ◦-semigroups
  9. recognisability ⊆ mso for ◦-words
  10. monads (slides)
  11. syntactic algebras for monads (slides)
  12. forest algebra
  13. algebra for graphs of bounded treewidth (slides)
  14. recognisability = mso for graphs of bounded treewidth (slides 1)
  15. 14 continued, same slides

Soft skills

These are some slides for my Scientist's Workshop lecture.

2017/2018

Algebraic language theory (automaty a półgrupy)

This course is about an alternative approach to regular languages, where one uses monoids (and more fancy algebraic structures) instead of automata.  I use notes from this lecture, but I hope to create a new version in pdf for this one (this has not materialised, I'm sorry). Lecture: Fridays 14:15-15:45 (room 4060) Exercises: Fridays 16:00-17:30 (room 4060) Exam The exam is oral. Here are the topic and some materials for them.
  1. Monoids and Green's relations 
  2. Factorisation forests
  3. First-order logic and LTL
  4. Omega and scattered words
  5. Countable words
  6. Monads
  7. What is an algebra for graphs and Courcelle's Theorem (also sections 3 and 4  here)
  8. Recognisability implies definability for bounded treewidth (these and these slides, also this paper if you reallly must)
Please email me to choose a time.  Choose any subset of the 8 topics in the list above, here is the exchange rate: • 3 topics: dostateczny • 4 topics: dobry • 6 topics: bardzo dobry

Advanced Topics in Automata 2017/2018 (Języki, Automaty i Obliczenia 2)

This lecture is a choice of slightly more advanced topics from automata theory. The lecture is on Tuesdays, 12:15 in room 5820. The exercises are on Wednesdays, 16:15 in room 5820, with Wojciech Czerwiński. Here is a plan of the lecture. There was a similar lecture last year and the year before that. This year we use lecture notes in pdf (some topics in the notes will not be covered by the lecture, and will not be on the exam). Here is the current version:

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.

Exam. The exam is an oral exam, which is mainly questions about the proofs of theorems. Please email me to choose a time, or better use this spreadsheet .You can improve your exam grade using the star exercises.  Choose any subset of the 8 topics in the list below, here is the exchange rate: • 2 topics: dostateczny • 3 topics: dobry • 4 topics: bardzo dobry
  1. Determinisation of $\omega$-automata
  2. Infinite duration games • Parity games in quasipolynomial time
  3. Tree-walking automata
  4. Distance automata • Vector Addition Systems
  5. Weighted automata over a field
  6. Decidability of the first-order theory of (R,+,*) no notes for this!
  7. Polynomial grammars
  8. Parsing in matrix multiplication time • Learning automata

2016/2017

Advanced Topics in Automata 2016/2017 (Języki, Automaty i Obliczenia 2)

This lecture is a choice of slightly more advanced topics from automata theory. The lecture is on Tuesdays, 12:15 in room 5820. The exercises are on Wednesdays, 16:15 in room 5820, with Wojciech Czerwiński. Here is a plan of the lecture. There was a similar lecture last year. Here are the topics for this year:
  1. automata on infinite words: determinisation
  2. games of infinite duration: the Büchi-Landweber theorem
  3. distance automata: decidability of limitedness
  4. treewidth and mso: Courcelle's theorem
  5. learning automata: the Angluin algorithm
  6. transducers
Exam. The exam is an oral exam, which is mainly questions about the proofs of theorems. Please email me to choose a time. You can improve your exam grade using the star exercises.  Choose any subset of the 6 topics in the list above, here is the exchange rate: • 2 topics: dostateczny • 3 topics: dobry • 4 topics: bardzo dobry

Infinite alphabets

This is a lecture on automata (and later other devices) that operate on infinite alphabets. The lecture is on Wednesdays at 12:15 in room 4060. The exercises are on Mondays at 14:15 in room 5050. The lecture and exercises are shared by Mikołaj Bojańczyk and Sławomir Lasota. Lecture notes Homework assignments Exam
  Here is an overview of the course Data words and their automata In the first half of the lecture, we discuss some concrete models, typically involving registers. The emptiness problem for most powerful of the models, data automata, will as hard as the famous reachability problem for vector addition systems, and the lecture will contain a description of the latter.
  1. Introduction to automata with registers
  2. Alternating automata with registers
  3. Data automata
  4. Logic on data words
  5. Reachability for vector addition systems
Sets with atoms In the second part of the lecture, we move to a more general setting, which describes some of the previous constructions in a cleaner mathematical model. This mathematical model will lead us to discover new questions.
  1. Sets with atoms and orbit-finiteness
  2. Automata in sets with atoms
  3. Atoms with structure other than equality
  4. Oligomorphism
  5. What is a computable function?
  6. Turing machines with atoms

Lipa

Lipa summer school 2017 (Warsaw, July 3-6)

The Lipa Summer School is a school on topics connected to logic in computer science. It is part of this grant. It was held in Warsaw, July 3-6 2017.  The school had 4 mini-courses given by:
  • Stephan Kreutzer (Berlin) Algorithmic meta-theorems (videos: 1, 2, 3, 4)
  • Joël Ouaknine (Saarbrücken) Decision Problems for Linear Recurrence Sequences (videos: 1234)
  • Moshe Vardi (Rice)  Linear-time verification and synthesis  (videos: 1234)
  • Mikołaj Bojańczyk (Warsaw, organiser) What is a recognisable language? (videos: 1234)
Each mini-course was 6 hours long (4 x 90 minutes). Here is the programme. Registration is closed. There will be free lunch and coffee breaks for registered participants, but not dinner (we will do an informal picnic on some evening without rain). The school is followed by ICALP.

Dates

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


Local information

The school was held at the University of Warsaw, in the Center of New Technologies, whose address is Banacha 2c. Be careful about the map on the Center's page, it's wrong, use the one below.   Picture of the conference venue and map below   A taxi from the airport should be around ≤ 20 PLN during the day (the official taxi queue is when you leave the airport, don't go with the people who whisper "taxi, taxi"). Here is a link for accessing the school from the airport using public transport (bus 175 or 188).  
The school is part of the grant Lipa that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 683080).

Lipa Summer School 2018 (June 25-28)

The Lipa Summer School is a school on topics connected to logic in computer science. It is part of this grant. This is the second edition, the first one was in 2017 (there are videos).  It will be held in Warsaw, June 25-28 2018.  The school consists of 4 mini-courses given by: Each mini-course is 6 hours long (4 x 90 minutes). Here is the program. Click on the talk titles to get descriptions and slides. There will be videos, but a few months after the school is over. Registration is free, and we might have a limited number of student dormitories for free.  We will likely (depending on the number of registrations) have  free lunch and coffee breaks for registered participants, but no dinner (we will do an informal picnic on some evening without rain).  

Dates

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

Venue

The school will be held in (room C of the) Auditorium Maximum of the university of Warsaw, in the historical center of Warsaw. Here is the building: Here is a map:
The school is part of the grant Lipa that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 683080).

2015/2016

Algebraic Language Theory

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.

Advanced Topics in Automata (Języki, Automaty i Obliczenia 2)

This lecture is a choice of slightly more advanced topics from automata theory. The lecture is on Tuesdays, 12:15 in room 5070. The exercises are on Wednesdays, 16:15 in in room 5820, with Wojciech Czerwiński.
  1. automata on infinite words: determinisation
  2. games of infinite duration: the Büchi-Landweber theorem
  3. weighted automata: decidable and undecidable problems
  4. distance automata: decidability of limitedness
  5. tree-walking automata: failure of determinisation
  6. transducers
  7. learning automata: the Angluin algorithm
  8. automata with infinite alphabets
  9. sets with atoms
Here are the star exercises and their solvers. Exam. The exam is an oral exam. Please email me to choose a time or use this link for Feb 15. Choose any subset of the 9 topics in the list above, here is the exchange rate: • 3 topics: dostateczny • 5 topics: dobry • 7 topics: bardzo dobry  

2014/2015

Algebraic Language Theory

This course is about an alternative approach to regular languages, where one uses monoids or semigroups instead of automata. Lecture: Tuesdays 8:45-10:15 (room 5070) Exercises: Tuesdays 10:25-11:55 (room 5070)

Języki i paradygmaty programowania

Laboratorium do wykładu Marcina Benke.

2013/2014

2011/2012

2009/2010

2008/2009