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

Sebastian Brandt, Yi‐Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky

Type: Preprint

Publication Date: 2021-01-01

Citations: 5

DOI: https://doi.org/10.48550/arxiv.2106.02066

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees	2022	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky
+	Local Problems on Grids from the Perspective of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics	2021	Jan Grebík Václav Rozhoň
+	Distributed Algorithms, the Lovász Local Lemma, and Descriptive Combinatorics	2020	Anton Bernshteyn
+ PDF Chat	Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics	2023	Anton Bernshteyn
+ PDF Chat	A Time Hierarchy Theorem for the LOCAL Model	2017	Yi‐Jun Chang Seth Pettie
+ PDF Chat	Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics	2023	Jan Grebík Václav Rozhoň
+	Distributed Algorithms, the Lov\'{a}sz Local Lemma, and Descriptive Combinatorics	2020	Anton Bernshteyn
+	On the Complexity of Local Distributed Graph Problems	2016	Mohsen Ghaffari Fabian Kühn Yannic Maus
+	Locally Checkable Problems in Rooted Trees	2021	Alkida Balliu Sebastian Brandt Yi‐Jun Chang Dennis Olivetti Jan Studený Jukka Suomela Aleksandr Tereshchenko
+ PDF Chat	An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model	2019	Yi‐Jun Chang Tsvi Kopelowitz Seth Pettie
+	A Time Hierarchy Theorem for the LOCAL Model	2017	Yi‐Jun Chang Seth Pettie
+ PDF Chat	A Time Hierarchy Theorem for the LOCAL Model	2019	Yi‐Jun Chang Seth Pettie
+	An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model	2016	Yi‐Jun Chang Tsvi Kopelowitz Seth Pettie
+	Deterministic coloring algorithms in the LOCAL model	2019	Dariusz R. Kowalski Piotr Krysta
+	Deterministic coloring algorithms in the LOCAL model.	2019	Dariusz R. Kowalski Piotr Krysta
+ PDF Chat	Local problems in trees across a wide range of distributed models	2024	Abhishek Dhar Eli Kujawa Henrik Lievonen Augusto Modanese Mikail Muftuoglu Jan Studený Jukka Suomela
+	On Homomorphism Graphs.	2021	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky
+	Deterministic Logarithmic Completeness in the Distributed Sleeping Model	2021	Leonid Barenboim Tzalik Maimon
+	Deterministic Logarithmic Completeness in the Distributed Sleeping Model	2021	Leonid Barenboim Tzalik Maimon
+	On Homomorphism Graphs	2021	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky

Works That Cite This (4)

Action	Title	Year	Authors
+ PDF Chat	One-ended spanning trees and definable combinatorics	2024	Matt Bowen Antoine Poulin Jenna Zomback
+	On Homomorphism Graphs	2021	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky
+	On Homomorphism Graphs.	2021	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky
+	Descriptive Combinatorics and Distributed Algorithms	2022	Anton Bernshteyn

Works Cited by This (93)

Action	Title	Year	Authors
+	Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem	1990	Miklós Laczkovich
+	A determinacy approach to Borel combinatorics	2015	Andrew Marks
+ PDF Chat	Short Cycles in Random Regular Graphs	2004	Brendan D. McKay Nicholas Wormald Beata Wysocka
+	Models of Random Regular Graphs	1999	N. C. Wormald
+ PDF Chat	A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels	2022	Péter Mester
+ PDF Chat	Factor of IID Percolation on Trees	2016	Mustazee Rahman
+	Independence ratio and random eigenvectors in transitive graphs	2015	Viktor Harangi Bálint Virág
+	Baire measurable paradoxical decompositions via matchings	2015	Andrew Marks Spencer Unger
+ PDF Chat	Toward more localized local algorithms: removing assumptions concerning global knowledge	2012	Amos Korman Jean‐Sébastien Sereni Laurent Viennot
+ PDF Chat	Poisson Thinning by Monotone Factors	2005	Karen Ball