Logic Seminar

Anton BernshteynCarnegie Mellon University
Descriptive combinatorics and distributed algorithms

Tuesday, April 28, 2020 - 2:55pm
Zoom

Descriptive combinatorics is the study of combinatorial problems (such as graph coloring) under additional topological or measure-theoretic regularity restrictions. It turns out that there is a close relationship between descriptive combinatorics and distributed computing, i.e., the area of computer science concerned with problems that can be solved efficiently by a decentralized network of processors. In this talk I will outline this relationship and present a number of applications.