Fetching the paper…
Reading the bibliography…
The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time.
On the computational complexity of algorithms
J. Hartmanis and R. E. Stearns · 1965
Earlier work this paper cites.
Data structures for distributed counting
M. Fürer · 1984
Earlier work this paper cites.
Deterministic coin tossing with applications to optimal parallel list ranking
R. Cole and U. Vishkin · 1986
Earlier work this paper cites.
Parallel tree contraction–Part I: Fundamentals
G. L. Miller and J. H. Reif · 1989
Earlier work this paper cites.
Ramsey Theory
R. L. Graham, B. L. Rothschild, and J. H. Spencer · 1990
Earlier work this paper cites.
A lower bound on probabilistic algorithms for distributive ring coloring
M. Naor · 1991
Earlier work this paper cites.
Locality in distributed graph algorithms
N. Linial · 1992
Earlier work this paper cites.
What can be computed locally?
M. Naor and L. J. Stockmeyer · 1995
Earlier work this paper cites.
On the complexity of distributed network decomposition
A. Panconesi and A. Srinivasan · 1996
Earlier work this paper cites.
Distributed Computing: A Locality-Sensitive Approach
D. Peleg · 2000
Earlier work this paper cites.
On the distributed complexity of computing maximal matchings
M. Hańćkowiak, M. Karoński, and A. Panconesi · 2001
Earlier work this paper cites.
On the complexity of distributed graph coloring
F. Kuhn and R. Wattenhofer · 2006
Earlier work this paper cites.
A constructive proof of the general Lovász local lemma
R. A. Moser and G. Tardos · 2010
Earlier work this paper cites.
Moser and Tardos meet Lovász
K. B. R. Kolipaka and M. Szegedy · 2011
Cited alongside, same era.
Towards a complexity theory for local distributed computing
P. Fraigniaud, A. Korman, and D. Peleg · 2013
Cited alongside, same era.
Toward more localized local algorithms: removing assumptions concerning global knowledge
A. Korman, J.-S. Sereni, and L. Viennot · 2013
Cited alongside, same era.
Survey of local algorithms
J. Suomela · 2013
Cited alongside, same era.
Random walks that find perfect objects and the Lovász local lemma
D. Achlioptas and F. Iliopoulos · 2014
Cited alongside, same era.
A constructive algorithm for the Lovász local lemma on permutations
D. G. Harris and A. Srinivasan · 2014
Cited alongside, same era.
An improved distributed algorithm for maximal independent set
M. Ghaffari · 2016
Later among the works it cites.
Locally checkable proofs in distributed computing
M. Göös and J. Suomela · 2016
Later among the works it cites.
Lopsidependency in the Moser-Tardos framework: Beyond the lopsided Lovász local lemma
D. G. Harris · 2016
Later among the works it cites.
Polynomial lower bound for distributed graph coloring in a weak LOCAL model
D. Hefetz, F. Kuhn, Y. Maus, and A. Steger · 2016
Later among the works it cites.
Commutativity in the algorithmic Lovász local lemma
V. Kolmogorov · 2016
Later among the works it cites.
Local computation: Lower and upper bounds
F. Kuhn, T. Moscibroda, and R. Wattenhofer · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Linear-in- Δ {\Delta} lower bounds in the LOCAL model
M. Göös, J. Hirvonen, and J. Suomela · 2015
Cited alongside, same era.
An algorithmic proof of the Lovász local lemma via resampling oracles
N. J. A. Harvey and J. Vondrák · 2015
Cited alongside, same era.
The locality of distributed symmetry breaking
L. Barenboim, M. Elkin, S. Pettie, and J. Schneider · 2016
Cited alongside, same era.
A lower bound for the distributed Lovász local lemma
S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto · 2016
Cited alongside, same era.
An exponential separation between randomized and deterministic complexity in the LOCAL model
Y.-J. Chang, T. Kopelowitz, and S. Pettie · 2016
Cited alongside, same era.
Survey of distributed decision
L. Feuilloley and P. Fraigniaud · 2016
Cited alongside, same era.
S. Brandt, J. Hirvonen, J. H. Korhonen, T. Lempiäinen, P. R. J. Östergård, C. Purcell, J. Rybicki, J. Suomela, and P. Uznanski · 2017
Closest in time.
Distributed algorithms for the Lovász local lemma and graph coloring
K.-M. Chung, S. Pettie, and H.-H. Su · 2017
Closest in time.
Deterministic distributed matching: Simpler, faster, better
M. Fischer and M. Ghaffari · 2017
Closest in time.
On the complexity of local distributed graph problems
M. Ghaffari, F. Kuhn, and Y. Maus · 2017
Closest in time.
Distributed degree splitting, edge coloring, and orientations
M. Ghaffari and H.-H. Su · 2017
Closest in time.
Parallel algorithms and concentration bounds for the Lovász local lemma via witness-DAGs
B. Haeupler and D. G. Harris · 2017
Closest in time.