STOC 2025 · 57th ACM Symposium on Theory of Computing, Prague, Czech Republic, June 2025 · doi:10.1145/3717823.3718211
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing:
We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these:
Michal Koucký and Nikhil Bansal (Eds.): STOC '25, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1295–1306, ACM Press, New York, 2025
ISBN 979-8-4007-1510-5