A lower bound for the distributed Lovász local lemma
From MaRDI portal
Publication:5361853
DOI10.1145/2897518.2897570zbMath1375.68191arXiv1511.00900OpenAlexW2243868910MaRDI QIDQ5361853
Orr Fischer, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Juho Hirvonen, Sebastian F. Brandt, Barbara Keller, Jara Uitto
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.00900
Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items
Constant space and non-constant time in distributed computing ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Improved distributed degree splitting and edge coloring ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Locally checkable problems in rooted trees ⋮ Component stability in low-space massively parallel computation ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Distributed coloring of hypergraphs ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Improved distributed \(\Delta\)-coloring ⋮ Almost global problems in the LOCAL model ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Unnamed Item ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ A topological perspective on distributed network algorithms ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Almost global problems in the LOCAL model ⋮ Local mending ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Distributed algorithms for fractional coloring ⋮ Distributed graph problems through an automata-theoretic Lens