Mini-Workshop: Descriptive Combinatorics, LOCAL Algorithms and Random Processes

  • Jan Grebík

    University of Warwick, Coventry, UK
  • Oleg Pikhurko

    University of Warwick, Coventry, UK
  • Anush Tserunyan

    McGill University, Montreal, Canada

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.

Cite this article

Jan Grebík, Oleg Pikhurko, Anush Tserunyan, Mini-Workshop: Descriptive Combinatorics, LOCAL Algorithms and Random Processes. Oberwolfach Rep. 19 (2022), no. 1, pp. 429–455

DOI 10.4171/OWR/2022/8