Measurable colorings, the Lovász Local Lemma, and distributed algorithms

Abstract: In the past twenty or so years, a rich theory has emerged concerning the behavior of graph colorings, matchings, and other combinatorial notions under additional regularity requirements, for instance measurability. It turns out that this area is closely related to distributed computing, i.e., the part of computer science concerned with problems that can be solved efficiently by a decentralized network of processors. A key role in this relationship is played by the Lovász Local Lemma and its analogs in the measurable setting. In this talk I will outline this relationship and present a number of applications.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.