The Library
Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
Tools
Tools
Tools
Grebík, Jan and Rozhon, Vaclav (2023) Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics. Advances in Mathematics, 431 . 109241. doi:10.1016/j.aim.2023.109241 ISSN 0001-8708.
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF (Updated version)
WRAP-local-problems-grids-perspective-distributed-algorithms-finitary-factors-combinatorics-updated-Grebik-2023.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only until 17 August 2024. Contact author directly, specifying your specific needs. - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1130Kb) |
|
PDF
WRAP-Local-problems-grids-perspective-distributed-algorithms-finitary-factors-combinatorics-23.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1094Kb) |
Official URL: https://doi.org/10.1016/j.aim.2023.109241
Abstract
We present an intimate connection among the following fields:
(a) distributed local algorithms: coming from the area of computer science,
(b) finitary factors of iid processes: coming from the area of analysis of randomized processes,
(c) descriptive combinatorics: coming from the area of combinatorics and measure theory.
In particular, we study locally checkable problems on grids from all three perspectives. Most of our results are for perspective (b) where we prove time hierarchy theorems similar to those known in the field (a) Chang and Pettie (2017) [16]. This approach, which borrows techniques from fields (a) and (c), implies a number of results about the possible complexities of finitary factor solutions. Among others, it answers three open questions of Holroyd et al. (2017) [46] or the more general question of Brandt et al. Brandt (2017) [9] who asked for a formal connection between the fields (a) and (b).
In general, we hope that our treatment will help to view all three perspectives as a part of a common theory of locality, in which we follow the insightful paper of Bernshteyn (2023) [6].
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Journal or Publication Title: | Advances in Mathematics | ||||||||
| Publisher: | Academic Press | ||||||||
| ISSN: | 0001-8708 | ||||||||
| Official Date: | 15 October 2023 | ||||||||
| Dates: |
|
||||||||
| Volume: | 431 | ||||||||
| Article Number: | 109241 | ||||||||
| DOI: | 10.1016/j.aim.2023.109241 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 1 August 2023 | ||||||||
| RIOXX Funder/Project Grant: |
|
||||||||
| Related URLs: | |||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
