Distributed graph problems through an automata-theoretic lens

DOI10.1016/j.tcs.2023.113710OpenAlexW4318069462MaRDI QIDQ2689441

Jukka Suomela, Yi-Jun Chang, Jan Studený

Publication date: 10 March 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113710

zbMATH Keywords

computational complexityautomata theorydistributed algorithmsalgorithm synthesisLOCAL modelLCL problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Improved upper bounds on synchronizing nondeterministic automata
• Unary finite automata vs. arithmetic progressions
• Finite automata and unary languages
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Complexity of the Frobenius problem
• Distributed graph problems through an automata-theoretic Lens
• Distributed coloring algorithms for triangle-free graphs
• The Locality of Distributed Symmetry Breaking
• Reset Sequences for Monotonic Automata
• The Frobenius Problem and Its Generalizations
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Degree Splitting, Edge Coloring, and Orientations
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• Synchronizing non-deterministic finite automata
• A Time Hierarchy Theorem for the LOCAL Model
• What Can be Computed Locally?
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Almost global problems in the LOCAL model
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• New classes of distributed time complexity
• A lower bound for the distributed Lovász local lemma
• LCL Problems on Grids
• How much does randomness help with locally checkable problems?
• Brief Announcement: Classification of Distributed Binary Labeling Problems

This page was built for publication: Distributed graph problems through an automata-theoretic lens