Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics

DOI10.1016/j.aim.2023.109241arXiv2103.08394OpenAlexW4385962964MaRDI QIDQ6076330

Jan Grebík, Václav Rozhoň

Publication date: 21 September 2023

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

local algorithmsdescriptive combinatoricsfinitary factors

Mathematics Subject Classification ID

Stationary stochastic processes (60G10) Graph theory (including graph drawing) in computer science (68R10) Descriptive set theory (03E15) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Theory of computing (68Qxx)

Related Items (1)

Combinatorics. Abstracts from the workshop held January 1--7, 2023

Cites Work

• Unnamed Item
• Measurable circle squaring
• Finitely dependent processes are finitary
• Borel structurability on the 2-shift of a countable group
• Borel chromatic numbers
• Finitary coloring
• Hyperfiniteness and Borel combinatorics
• A bound on measurable chromatic numbers of locally finite Borel graphs
• Borel circle squaring
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Countable abelian group actions and hyperfinite equivalence relations
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• A determinacy approach to Borel combinatorics
• FINITELY DEPENDENT COLORING
• A coloring property for countable groups
• Locality in Distributed Graph Algorithms
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• An Improved Distributed Algorithm for Maximal Independent Set
• Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem
• What Can be Computed Locally?
• Exponential Separations in the Energy Complexity of Leader Election
• On the complexity of local distributed graph problems
• Borel Combinatorics of Locally Finite Graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• New classes of distributed time complexity
• Distributed Maximal Independent Set using Small Messages
• A lower bound for the distributed Lovász local lemma
• LCL Problems on Grids
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS
• Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of BFS in Radio Networks
• Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• How long it takes for an ordinary node with an ordinary ID to output?
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics

This page was built for publication: Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics