Brief Announcement: Classification of Distributed Binary Labeling Problems

DOI10.1145/3382734.3405703MaRDI QIDQ5855255zbMATH OpenOpenAlexWikidataFDO

Authors Alkida Balliu, Sebastian F. Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.13294, https://aaltodoc.aalto.fi/handle/123456789/111066

zbMATH Keywords

distributed computational complexitygraph problemsLOCAL modellocally checkable labeling problems

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Recommendations

• Classification of distributed binary labeling problems
• Graph labelings derived from models in distributed computing: A complete complexity classification
• New classes of distributed time complexity
• Almost global problems in the LOCAL model
• Almost global problems in the LOCAL model

Cited in

(12)

• Linial for lists
• Distributed algorithms for fractional coloring
• Distributed graph problems through an automata-theoretic Lens
• Distributed graph problems through an automata-theoretic lens
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• Distributed Data Structures: A Survey on Informative Labeling Schemes
• Distributed Lower Bounds for Ruling Sets
• Factor-of-iid balanced orientation of non-amenable graphs
• Local conflict coloring revisited: Linial for lists
• Classification of distributed binary labeling problems
• The complexity landscape of distributed locally checkable problems on trees
• Exponential speedup over locality in \textsf{MPC} with optimal memory

This page was built for publication: Brief Announcement: Classification of Distributed Binary Labeling Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855255)