Descriptive Combinatorics and Distributed Algorithms
From MaRDI portal
Abstract: This is a draft of an article to appear in the October 2022 issue of the Notices of the AMS. In this survey article we explore a fascinating area called descriptive combinatorics and its recently discovered connections to distributed algorithms -- a fundamental part of computer science that is becoming increasingly important in the modern era of decentralized computation. In the first part of the article we give a brief introduction to some of the central notions and problems of descriptive combinatorics. The second part is devoted to an overview of some of the results concerning the interactions between descriptive combinatorics and distributed algorithms, as well as a few open problems. The article should be accessible to readers with little to no background in either descriptive set theory or computer science.
Recommendations
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- scientific article; zbMATH DE number 1418337
- Borel combinatorics of locally finite graphs
- Combinatorial algorithms for distributed graph coloring
Cited in
(4)- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- A combinatorial characterization of the distributed 1-solvable tasks
- Complexity of finite Borel asymptotic dimension
- Borel local lemma: arbitrary random variables and limited exponential growth
This page was built for publication: Descriptive Combinatorics and Distributed Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5059747)
