CISPA
Browse
cispa_all_3651.pdf (746.89 kB)

The landscape of distributed complexities on trees and beyond

Download (746.89 kB)
conference contribution
posted on 2023-11-29, 18:20 authored by Christoph Grunau, Václav Rozhoň, Sebastian BrandtSebastian Brandt
We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below log* n. Our contribution is threefold: - Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity o(log* n) has actually complexity O(1). This result improves upon the previous speedup result from o(log log* n) to O(1) by [Chang, Pettie, FOCS 2017]. - In the related LCA and VOLUME models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020], we prove the same speedup from o(log* n) to O(1) for all bounded degree graphs. - Similarly, we complete the classification of the LOCAL complexity landscape of oriented d-dimensional grids by proving that any LCL problem with local complexity o(log* n) has actually complexity O(1). This improves upon the previous speed-up from o((log* n)^{1/d}) by Suomela in [Chang, Pettie, FOCS 2017].

History

Preferred Citation

Christoph Grunau, Václav Rozhoň and Sebastian Brandt. The landscape of distributed complexities on trees and beyond. In: ACM Symposium on Principles of Distributed Computing (PODC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Symposium on Principles of Distributed Computing (PODC)

Legacy Posted Date

2022-05-05

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3651, title = "The landscape of distributed complexities on trees and beyond", author = "Grunau, Christoph and Rozhoň, Václav and Brandt, Sebastian", booktitle="{ACM Symposium on Principles of Distributed Computing (PODC)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC