Locally Checkable Problems: Distance, Volume, and Beyond

16^th December 2025, 12:00 ALT
Will Rosenbaum

Abstract

Locally Checkable Labeling Problems (LCLs) are problems defined on bounded degree graphs in which a valid solution can be verified by examining a constant radius neighborhood around each vertex in the graph. Familiar examples include computing maximal independent sets, maximal matchings, and proper colorings. While many of these problems admit simple efficient algorithms in the centralized setting, their complexities in distributed models of computation have been the subject of extensive study.

In this talk, I will give an overview of the landscape of complexities of LCLs in two distributed models of computation: the classical LOCAL model and the more recent VOLUME model. I will then discuss progress, challenges, and approaches to generalizing the results for LCLs beyond bounded degree graphs.