CISPA
Browse
cispa_all_3542.pdf (1.5 MB)

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

Download (1.5 MB)
conference contribution
posted on 2023-11-29, 18:19 authored by Sebastian BrandtSebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozho?, Zoltán Vidnyánszky
We study connections between three different fields: distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics. We focus on two central questions: Can we apply techniques from one of the areas to obtain results in another? Can we show that complexity classes coming from different areas contain precisely the same problems? We give an affirmative answer to both questions in the context of local problems on regular trees: 1. We extend the Borel determinacy technique of Marks [Marks - J.Am.Math.Soc.2016] coming from descriptive combinatorics and adapt it to the area of distributed computing, thereby obtaining a more generally applicable lower bound technique in descriptive combinatorics and an entirely new lower bound technique for distributed algorithms. Using our new technique, we prove deterministic distributed Omega(log n)-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique [Brandt - PODC 2019] responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest; in fact, it has already played an important role in a new lower bound for the Lovász local lemma in the Local Computation Algorithms model from sequential computing [Brandt, Grunau, Rozhoň - PODC 2021]. 2. We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity O(log n), extending the classification of Baire measurable colorings of Bernshteyn [Bernshteyn - personal communication]. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in O(log n) rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution. We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn - arXiv 2004.04905].

History

Preferred Citation

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozho? and Zoltán Vidnyánszky. Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. In: Innovations in Theoretical Computer Science (ITCS). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Innovations in Theoretical Computer Science (ITCS)

Legacy Posted Date

2021-12-14

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3542, title = "Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics", author = "Brandt, Sebastian and Chang, Yi-Jun and Grebík, Jan and Grunau, Christoph and Rozho?, Václav and Vidnyánszky, Zoltán", booktitle="{Innovations in Theoretical Computer Science (ITCS)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC