Brief announcement: Round eliminator: a tool for automatic speedup simulation. (English) Zbl 07323209
Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 352-354 (2020).
Keywords:
LOCAL model; automatic lower bounds; automatic upper bounds; graph problems; locally checkable problems; round elimination; speedup simulationReferences:
| [1] | Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. 2019. Classification of distributed binary labeling problems. CoRR abs/1911.13294 (2019). · Zbl 1540.68163 |
| [2] | Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. 2019. Lower bounds for maximal matchings and maximal independent sets. In Proc. 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019). IEEE, 481-497. · Zbl 1499.68248 |
| [3] | Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. 2020. Distributed Lower Bounds for Ruling Sets. CoRR abs/2004.08282 (2020). · Zbl 1539.68371 |
| [4] | Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, and Jukka Suomela. 2019. Locality of Not-so-Weak Coloring. In Proc. 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019) (Lecture Notes in Computer Science, Vol. 11639). Springer, 37-51. · Zbl 1534.68138 |
| [5] | Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. 2019. Hardness of Minimal Symmetry Breaking in Distributed Computing. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019). ACM Press, 369-378. · Zbl 07298699 |
| [6] | Sebastian Brandt. 2019. An Automatic Speedup Theorem for Distributed Problems. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019). ACM Press, 379-388. · Zbl 07298700 |
| [7] | Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. 2016. A lower bound for the distributed Lovász local lemma. In Proc. 48th ACM Symposium on Theory of Computing (STOC 2016). ACM Press, 479-488. · Zbl 1375.68191 |
| [8] | Sebastian Brandt and Dennis Olivetti. 2020. Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants. In Proc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020). ACM Press. · Zbl 07323172 |
| [9] | Nathan Linial. 1992. Locality in Distributed Graph Algorithms. SIAM J. Comput. 21, 1 (1992), 193-201. · Zbl 0787.05058 |
| [10] | Moni Naor. 1991. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics 4, 3 (1991), 409-412. · Zbl 0738.68007 |
| [11] | Dennis Olivetti. 2020. Round Eliminator: a tool for automatic speedup simulation. https://github.com/olidennis/round-eliminator · Zbl 07323209 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
