Metadata only
Date
2021-07Type
- Conference Paper
Abstract
The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's output. In this paper we show that the randomized LCA complexity of the Lovász Local Lemma (LLL) on constant degree graphs is Θ(log n). The lower bound follows by proving an ω(log n) lower bound for the Sinkless Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a question of [Rosenbaum, Suomela PODC 2020]. Additionally, we show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of o(glog n ) can be turned into a deterministic LCA algorithm with a probe complexity of O(log∗n). This improves exponentially upon the currently best known speed-up result from o(log log n) to O(log∗n) implied by the result of [Chang, Pettie FOCS 2017] in the LOCAL model. Finally, we show that for every fixed constant c ≥ 2, the deterministic VOLUME complexity of c-coloring a bounded degree tree is Θ(n), where the VOLUME model is a close relative of the LCA model that was recently introduced by [Rosenbaum, Suomela PODC 2020]. Show more
Publication status
publishedExternal links
Book title
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)Pages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
Local Computation Algorithms; Lovász Local Lemma; VOLUME Model; Gap ResultOrganisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
More
Show all metadata