Exponential Speedup Over Locality in MPC with Optimal Memory

Alkida Balliu, Sebastian Brandt, Manuela Fischer +4

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example p…