Algomanet - summer 2023

Basic information

The two Algomanet courses scheduled for the spring 2023 will take place in the week June 26-30 at Masaryk University in Brno. The courses will be delivered on site only, starting at 9am on Monday June 26 and concluding in late afternoon on Friday June 30.

The registration is now open. You can register by sending an e-mail to Darina Boukalová (boukalova@fi.muni.cz) before the deadlines noted below. It is possible to register for both or just one of the two courses offered. The courses are primarily intended for those affiliated with the participating universities, however, we will be able to offer a limited number of places to students from other universities, too.

• Registration deadline when requesting financial support: Monday April 3, 2023
• General registration deadline: Monday May 15, 2023

Schedule

All lectures and exercices take part in the building of the Faculty of Informatics located at Botanická 68a, Brno.

Monday June 26

Tuesday June 27

Wednesday June 28

Thursday June 29

Friday June 30

Jan Křetínský: Probabilistic verification

This course provides a tutorial on analysis of basic probabilistic models such as Markov chains, Markov decision processes, and stochastic games. These are classical models for applications ranging from decision making under uncertainty (as in AI or game theory), to reliability analysis (e.g., of network protocols or power plants), to design of biochemical experiments, to synthesis of controllers (of embedded and cyber-physical systems).

Verification aims at reliable analysis of these models with respect to different properties. For instance, qualitative properties such as "Is a given state reached with probability 1?" or quantitative questions such as "What is the probability that a given logical specification is satisfied?" or synthesis questions such as "What is the optimal resolution of decisions in order to maximize the frequency of visiting a given state?"

The lectures will focus on the algorithmic aspects of the analysis, in particular on graph-based and numerical algorithms rather than on probability theory. This includes classical algorithms such as the attractor construction, linear programming, dynamic programming (value iteration, policy iteration), which relate to approximate dynamic programming, reinforcement learning, or probabilistic planning. Besides, we discuss recent results on the reliability of these algorithms.

We shall cover the whole spectrum of results: from the theoretical computational complexity over the mentioned algorithms to their practical properties and recent heuristics combining rigorous mathematical guarantees and practical efficiency of machine learning.

Pascal Schweitzer: Algorithms for permutation groups

Groups are the mathematical objects that capture the symmetry of combinatorial objects. Algorithmic group theory investigates which computational tasks involving groups have efficient solutions. The goal is to develop theoretically and practically efficient algorithms.

In contrast to graph theory, when it comes to questions of polynomial-time solvability in computational group theory, the way we encode the groups in the computer is crucial. Groups can for example be represented explicitly by their multiplication tables, more compactly as permutation groups, or by so-called presentations. The course briefly discusses these differences but then focuses on permutation group algorithms, which often arise naturally when dealing with finite graphs.

For permutation groups, many non-trivial polynomial-time algorithms have been developed. We will discuss efficient algorithms for various tasks. Some are seemingly easy at first sight but need clever techniques. An example is the membership problem, which asks us to decide whether a given permutation is contained in a permutation group given by generators.

The course will also hint at how algorithms for permutation groups are used to develop fast algorithms for the graph isomorphism problem. This is for example done in Luks's polynomial-time algorithm for isomorphism of bounded degree graphs and Babai's quasipolynomial-time algorithm.