# AlgoMaNet – Algorithms and Mathematics Network

AlgoMaNet is a network based on a collaboration among four Central European universities (Charles University in Prague, Jagiellonian University in Kraków, Masaryk University in Brno and the University of Warsaw) in the areas of discrete algorithms, discrete mathematics and theoretical computer science. The network offers lectures on advanced topics primarily to MSc and PhD students affiliated with one of the four universities. The aims of the program resemble those of the intensive programs for senior undergraduate and graduate students organized by Charles University in 2014, in 2016 and 2018. The registration for the courses in the spring 2020 has been closed.

## Courses offered in the academic year 2019/20

In the academic year 2019/20, there will be seven intensive courses. The courses are organized in two-week blocks, and it is possible (and actually expected) to attend only some of the seven courses. Three courses are offered as intensive courses with a lecture held on each weekday during the two-week block, two as one-week courses with two lectures each day, and two as one-week courses with a single lecture each day. A part of each weekday will be also devoted to solving exercises given during the lectures. While the schedule will allow one to attend all courses in a block, it is possible to register for a single course in the block.

**January 13-January 24, University of Warsaw**

Mikołaj Bojańczyk (University of Warsaw): Automata, semigroups and logic (Jan 13-17)

Michał Pilipczuk (University of Warsaw): Combinatorics and algorithms for sparse graphs (Jan 20-24)**January 27-February 7, Masaryk University, Brno**

Andrzej Grzesik (JU Kraków): Extremal graph theory

Petr Hliněný (MU Brno): Topological and geometric graph theory (half course, Feb 3-7)

Dan Kráľ (MU Brno): Regularity method (half course, Jan 27-31)**May 4-May 15, Charles University, Prague**

Pavel Hubáček (Charles University): Foundations of theoretical cryptography

Michal Koucký (Charles University): Fine-grained complexity

##### Syllabus for the course "Automata, semigroups and logic"

For a language of finite words, the following conditions are equivalent: (a) it is regular, i.e. recognised by a finite automaton; (b) it can be defined by a formula of monadic second-order logic; (c) it is recognised by a homomorphism into a finite semigroup. I will talk about these connections, with a certain emphasis on the semigroups in item (c). In particular, I would like to talk about Green’s relations, which explain much of the behaviour of finite semigroups.

##### Syllabus for the course "Combinatorics and algorithms for sparse graphs"

The course will be an introduction to the theory of sparse graphs, a young branch of graph theory that studies abstract notions of structural sparseness in graphs. After introducing the main concepts - bounded expansion and nowhere denseness - we will present several combinatorial methods and viewpoints that are fundamental for the theory, including generalized coloring numbers, low treedepth colorings, neighborhood complexity, and uniform quasi-wideness. We will also show some applications of those techniques in algorithm design and in algorithmic finite model theory.

##### Syllabus for the course "Extremal graph theory"

The course will cover basic concepts in the extremal graph theory, including Turán's theorem and its generalizations, as well as important methods related with bipartite Turán problems and techniques of embedding large (spanning) graphs. Except the classical theorems, some recent results and open problems will be also presented.

##### Syllabus for the course "Topological and geometric graph theory"

This short course will provide basic knowledge of topological graph theory. This includes surfaces and graphs embedded in them, cycles in embedded graphs and some other embedding properties, and embedding density. In addition to classical topological graph questions, we will address the particular problem of graph crossing number, and focus on the related structural results including the very recent progress in the area. Lastly, we will mention several interesting questions of geometric representations of graphs.

Prerequisities: We assume mild undergraduate knowledge of topology (continuous maps, limits, compactness, homeomorphisms) and of graphs (minors, planar graphs, Euler's formula).

##### Syllabus for the course "Regularity method"

The regularity method is one of the most important tools in modern combinatorics. Szemerédi's Regularity Lemma from the late 1970s asserts that every graph can be partitioned into a bounded number of parts that mutually interact in a pseudorandom way. This important result has found many applications in various areas of mathematics and computer science, in particular, in extremal combinatorics and property testing, and has been generalized from the graph setting to many other combinatorial objects.

During the lectures, we will present the Regularity Lemma and its counting counterpart, the Removal Lemma, in the setting of graphs, groups, hypergraphs and permutations. We will also present a direct proof of the Removal Lemma for graphs by Fox and several applications of the regularity method in extremal combinatorics.

##### Syllabus for the course "Foundation of theoretical cryptography"

The central aim of modern theoretical cryptography is to characterize the minimal necessary assumptions for solving a particular cryptographic task. This course introduces general cryptographic assumptions and their applications in constructions of cryptographic primitives and provably secure protocols.

- Basics
- one-time pad, perfect security, computational security, indistinguishability
- pseudorandom generators and computational one-time pad
- pseudorandom functions and permutations

- Data integrity
- message authentication codes and cryptographic hashing
- signature schemes
- applications in distributed cryptographic currencies: Bitcoin

- Zero-knowledge
- definitions and basic protocols
- commitment schemes
- applications in cryptographic currencies: Zerocash

##### Syllabus for the course "Fine-grained complexity"

The series of lectures will provide a tutorial on fine-grained complexity. Fine-grained complexity which emerged over the past decade maps the landscape of problems solvable in polynomial time, and provides insight into their exact asymptotic complexities. By building a formal connection between the complexity of problems like the Longest Common Subsequence and the complexity of solving NP-complete problems such as SAT it provides a plausible explanation why despite lots of effort we did not manage to improve on the trivial quadratic or cubic algorithms for such problems. The course will cover the Strong Exponential Time Hypothesis (SETH) and its variants, problems in P such as Orthogonal Vectors Problem, 3SUM, Longest Common Subsequence and many others, and exhibit a striking relationships between their complexities.

## Contact details

The program is overseen by the steering committee assisted by Darina Boukalová (`boukalova`**q1l33ij=d**@fi**Ij3xOBGHv**.muni**j_TsWsiaD**.cz

) from Masaryk University, Brno.
#### Steering committee

- Zdeněk Dvořák (Charles University, Prague)
- Daniel Kráľ (Masaryk University, Brno)
- Szymon Toruńczyk (University of Warsaw)
- Bartosz Walczak (Jagiellonian University, Kraków)

## Registration

The registration is free.
To register, send an e-mail to Darina Boukalová (`boukalova`

)
by **xcsDl7uL3**@fi**s7sR3qLPH**.muni**_PfCdU9aq**.cz~~October 18, 2019~~ **October 22, 2019**.
Please register even if you intend to attend a locally organized course.
In your registration e-mail, please indicate
who you are (your name and affiliation in particular),
which lectures you would like to attend and
what level of support is necessary for you to participate.

We may be able to accept registrations by students not affiliated with either of the four universities in the network. These registrations will be confirmed after the registration deadline if space constraints permit.