New Hardness Results for the LOCAL Model via a Simple Self-Reduction
Open Access
- 6 July 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 301-310
Abstract
No abstract availableAll Related Versions
Funding Information
- MUR, FIS 3 (D53C25002470001)
This publication has 25 references indexed in Scilit:
- Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching2025
- Fast algorithms for Vizing's theorem on bounded degree graphsJournal of Combinatorial Theory, Series B, 2025
- A fast distributed algorithm for (Δ + 1)-edge-coloringJournal of Combinatorial Theory, Series B, 2022
- Lower Bounds for Maximal Matchings and Maximal Independent Sets2019
- The Complexity of Distributed Edge Coloring with Small Palettes2018
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model2016
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- A Lower Bound on Probabilistic Algorithms for Distributive Ring ColoringSIAM Journal on Discrete Mathematics, 1991
- The Isoperimetric Number of Random Regular GraphsEuropean Journal of Combinatorics, 1988
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980