Abstract: Starting in the 1950’s, Tutte conjectured sufficient conditions for the existence of nowhere-zero 3-flows, 4-flows, and 5-flows in graphs. In this short course we will be motivated by these three conjectures as we learn about the nature of integer flows. Starting from the basics and moving towards recent developments, we will see that this topic intersects huge swaths of both chromatic and structural graph theory.

Abstract:Starting with the classical marriage setting by Gale and Shapley, matching markets have been used to model many (mostly two-sided) scenarios, where agents (students and schools, doctors and hospitals, workers and firms,…) need to be paired to each other, and the quality of the solution is measured using fairness criteria. In this short course, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.

Abstract:
Distributed computing is the field of computer science that studies how a collection of autonomous computing entities can cooperate in the absence of a centralized coordinator, to efficiently achieve a common objective. This field therefore addresses fundamental issues related to very many different frameworks, from multicore architectures to cloud computing and data centers, and from technological artifacts (e.g., networks) to biological systems (e.g., colonies of insects). The large number of application domains has resulted in a plethora of distributed computing models, often exhibiting very different features, and each dedicated to some specific applications. Nevertheless, distributed computing remains mostly guided by a reasonably small number of fundamental principles, and the objective of this course is to provide the students with some of the most important principles forming the pillars of distributed computing.

More specifically, the course will address several algorithmic aspects of distributed computing, from a combinatorial perspective. Indeed, even if distributed computing is dealing with issues like asynchrony in computation, presence of various types of failures, and with a large variety of communication media (shared memory, message passing, network, etc.), combinatorics play a significant role in the design and analysis of distributed algorithms, especially as far as lower bounds are concerned. The course will mostly focus on two different standard (classes of) models of distributed computing, namely asynchronous shared memory with crash failures, and synchronous failure-free networks. For each of these two (classes of) models, the course will provide examples of algorithms and lower bounds for which combinatorics play a crucial role.

In particular, a part of the course will focus on consensus, arguably one of the most important task in the context of distributed systems, strongly related to systems like blockchain. The impossibility of achieving consensus in asynchronous systems subject to crash failures will be an opportunity to demonstrate the role of algebraic topology in the analysis of distributed algorithms. Another part of the course will focus on graph problems such as computing a maximal independent set (MIS), which is a central symmetry-breaking task in the context of network computing. The design of a lower bound on the round-complexity of computing MIS in synchronous networks will be an opportunity to relate the analysis of distributed algorithm with the study of graph theoretic parameters such as the chromatic number of a graph. Beyond combinatorics, the course will also show tight connections between distributed computing and other fields of computer science, such as communication complexity.