Departmental Colloquium
Anton Bernshteyn
Georgia Tech
Distributed computing and descriptive combinatorics
Abstract: In this talk I will discuss a recently discovered connection between two seemingly very disparate fields: distributed computing and descriptive combinatorics. Distributed computing is the area of computer science concerned with problems that can be solved efficiently by a (finite) decentralized network of processors. Descriptive combinatorics, on the other hand, studies combinatorial problems on infinite graphs under additional topological or measure-theoretic regularity constraints and is largely motivated by questions in set theory, ergodic theory, and topological dynamics. It turns out that these two areas are intimately related to each other, and there are formal ways of translating results from one context to the other one. I will survey what is known about this connection and outline some open problems.
Friday January 19, 2024 at 3:00 PM in 636 SEO