Descriptive Combinatorics, LOCAL Algorithms and Random Processes

Abstract

The aim of this mini-workshop was to discover and deepen connections between the fields of descriptive combinatorics, distributed computing and random processes. The common link is played by the so-called local coloring problems on graphs, where the validity of solution can be checked locally, and the common interest can be phrased as the following central question: Is it possible to produce a solution to a given local problem efficiently? While all three areas possess a solid background that was achieved by decades of intense research, a systematic study of formal connections between them is a recent emerging phenomenon. This approach has already proved to be very fruitful: several open questions in each of the fields were solved by means and techniques of the other two. The purpose of this meeting is to bring together researchers in all three fields in order to explore these exciting connections.