Topological and combinatorial methods in Theoretical Distributed Computing

Workshop on Topology: Identifying Order in Complex Systems
Topic:Topological and combinatorial methods in Theoretical Distributed Computing
Speaker:Dmitry Feichtner-Kozlov
Affiliation:Institute for Algebra, Geometry, Topology, and their Applications, University of Bremen
Date:Saturday, November 7
Time/Room:2:00pm - 3:00pm/S-101
Video Link:https://video.ias.edu/wtocs/-Kozlov

In the first half of the talk I will give a very compressed introduction into parts of Theoretical Distributed Computing from the point of view of mathematician. I will describe how to construct simplicial models whose combinatorics contains important information about computability and complexity of standard distributed tasks. In the second part, I will outline our recent progress on estimating the complexity of the so-called Weak Symmetry Breaking task, where we are able to derive some quite surprising results. At the technical core of our argument we need to construct complete matchings on specific graphs associated to the so-called iterated standard chromatic subdivision of a simplex. The talk is based on our monograph "Distributed Computing through Combinatorial Topology" (with Herlihy and Rajsbaum), as well as on a recent series of preprints.