New classes of distributed time complexity

DOI10.1145/3188745.3188860zbMath1427.68094arXiv1711.01871OpenAlexW2962850638WikidataQ130891484 ScholiaQ130891484MaRDI QIDQ5230383

Jukka Suomela, Tuomo Lempiäinen, Alkida Balliu, Dennis Olivetti, Juho Hirvonen, Janne H. Korhonen

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.01871

zbMATH Keywords

graph algorithmsLOCAL modeldistributed complexity theorylocally checkable labellings

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Related Items (7)

Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Locally checkable problems in rooted trees ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Almost global problems in the LOCAL model ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Local mending ⋮ Distributed graph problems through an automata-theoretic Lens

This page was built for publication: New classes of distributed time complexity