Distributed graph problems through an automata-theoretic lens

DOI10.1016/J.TCS.2023.113710MaRDI QIDQ2689441zbMATH OpenOpenAlexFDO

Authors Yi-Jun Chang, Jan Studený, Jukka Suomela

Publication date 10 March 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexitydistributed algorithmsautomata theoryalgorithm synthesisLOCAL modelLCL problems

Mathematics Subject Classification ID

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

Recommendations

• Brief announcement: Distributed graph problems through an automata-theoretic lens
• What Can be Computed Locally?
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• LCL problems on grids
• Locality in Distributed Graph Algorithms

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• scientific article; zbMATH DE number 2213327 (Why is no real title available?)
• A lower bound for the distributed Lovász local lemma
• A time hierarchy theorem for the LOCAL model
• Almost global problems in the LOCAL model
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Complexity of the Frobenius problem
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Descriptional and computational complexity of finite automata -- a survey
• Deterministic coin tossing with applications to optimal parallel list ranking
• Directable nondeterministic automata
• Distributed Computing: A Locality-Sensitive Approach
• Distributed coloring algorithms for triangle-free graphs
• Distributed degree splitting, edge coloring, and orientations
• Distributed graph problems through an automata-theoretic Lens
• Finite automata and unary languages
• How much does randomness help with locally checkable problems?
• Improved upper bounds on synchronizing nondeterministic automata
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• New classes of distributed time complexity
• Parallel Symmetry-Breaking in Sparse Graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Reset Sequences for Monotonic Automata
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Synchronizing non-deterministic finite automata
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• The Frobenius Problem and Its Generalizations
• The locality of distributed symmetry breaking
• Unary finite automata vs. arithmetic progressions
• What Can be Computed Locally?

Cited in

(2)

• Extended dependency graphs and efficient distributed fixed-point computation
• Brief announcement: Distributed graph problems through an automata-theoretic lens

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

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