Separating complexity classes of LCL problems on grids

2025/01/29 by Katalin Berlow, Berlow, Katalin, Anton Bernshteyn +5 · 1 voice · 2 citations
Computer Science · #Coding theory and cryptography #Cellular Automata and Applications #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.2501.17445

Abstract

We study the complexity of locally checkable labeling (LCL) problems on ℤⁿ from the point of view of descriptive set theory, computability theory, and factors of i.i.d. Our results separate various complexity classes that were not previously known to be distinct and serve as counterexamples to a number of natural conjectures in the field.

Cited by

• Borel Combinatorics of Schreier Graphs of ℤ-actions
• Borel Polychromatic Number of Grids

Discussions

• Holy crap, you REALLY CAN attack complexity theory via measure theory...if you go deep enough into the weeds of descriptive set theory. Welp, I guess I know what I need to start digging into as soon a [bsky, 13 points, 2 comments]

Related

• LCL problems on grids
• The Landscape of Distributed Complexities on Trees and Beyond
• Locally Checkable Labelings with Small Messages
• The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees
• The Complexity Landscape of Distributed Locally Checkable Problems on Trees