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




Related Items

Constant space and non-constant time in distributed computingNetwork Decomposition and Distributed Derandomization (Invited Paper)Improved distributed degree splitting and edge coloringDerandomizing local distributed algorithms under bandwidth restrictionsNode and edge averaged complexities of local graph problemsLocal problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatoricsLocally checkable problems in rooted treesComponent stability in low-space massively parallel computationProbabilistic constructions in continuous combinatorics and a bridge to distributed algorithmsDistributed $(\Delta+1)$-Coloring via Ultrafast Graph ShatteringDistributed graph problems through an automata-theoretic lensDistributed coloring of hypergraphsMini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL ModelFooling views: a new lower bound technique for distributed computations under congestionImproved distributed \(\Delta\)-coloringAlmost global problems in the LOCAL modelA Time Hierarchy Theorem for the LOCAL ModelUnnamed ItemHow long it takes for an ordinary node with an ordinary ID to output?A topological perspective on distributed network algorithmsDistributed algorithms for the Lovász local lemma and graph coloringAlmost global problems in the LOCAL modelLocal mendingDistributed Lower Bounds for Ruling SetsLinial for listsDistributed algorithms for fractional coloringDistributed graph problems through an automata-theoretic Lens