Brandt, Sebastian, Chang, Yi-Jun, Grebik, Jan, Grunau, Christoph, Rozhon, Vaclav and Vidnyanszky, Zoltan (2022) Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Berkeley, CA, USA, 31 Jan - 03 Feb 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 215 29:1-29:26. ISBN 978-3-95977-217-4. doi:10.4230/LIPIcs.ITCS.2022.29 ISSN 1868-8969.

Preview

PDF WRAP-Local-problems-on-trees-from-the-perspectives-of-distributed-algorithms-Grebik-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1306Kb) | Preview

Request Changes to record.

Abstract

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 Ω(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].

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Trees (Graph theory) , Distributed algorithms , Combinatorial set theory, Homomorphisms (Mathematics)
Series Name:	Leibniz International Proceedings in Informatics (LIPIcs)
Journal or Publication Title:	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher:	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of Publication:	Dagstuhl, Germany
ISBN:	978-3-95977-217-4
ISSN:	1868-8969
Official Date:	25 January 2022
Dates:	Date Event 25 January 2022 Published 31 October 2021 Accepted
Volume:	215
Page Range:	29:1-29:26
Article Number:	29
DOI:	10.4230/LIPIcs.ITCS.2022.29
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	29 March 2022
Date of first compliant Open Access:	30 March 2022
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID UNSPECIFIED Walter Haefner Foundation UNSPECIFIED UNSPECIFIED ETH Zürich Foundation https://eth-its.ethz.ch/ RPG-2018-424 Leverhulme Trust http://dx.doi.org/10.13039/501100000275 853109 European Research Council http://dx.doi.org/10.13039/501100000781 113047 National Research, Development and Innovation Office https://nkfih.gov.hu/ 129211 National Research, Development and Innovation Office https://nkfih.gov.hu/ M2779 National Research, Development and Innovation Office https://nkfih.gov.hu/
Conference Paper Type:	Paper
Title of Event:	13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Type of Event:	Conference
Location of Event:	Berkeley, CA, USA
Date(s) of Event:	31 Jan - 03 Feb 2022
Related URLs:	Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads