Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems

Will Rosenbaum, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Assume we have a graph problem that is locally checkable but not locally solvable - -given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a feasible solution each node needs to explore the input graph at least up to distance Ω (log n) in order to produce its own part of the solution. Such problems have been studied extensively in the recent years in the area of distributed computing, where the key complexity measure has been distance: how far does a node need to see in order to produce its own part of the solution. However, if we are interested in e.g. sublinear-time centralized algorithms, a much more appropriate complexity measure would be volume: how large a subgraph does a node need to see in order to produce its own part of the solution. In this work we study locally checkable graph problems on bounded-degree graphs and we give a number of constructions that exhibit different tradeoffs between deterministic distance, randomized distance, deterministic volume, and randomized volume: • If the deterministic distance is linear, it is also known that randomized distance is near-linear. We show that volume complexity is fundamentally different: there are problems with a linear deterministic volume but only logarithmic randomized volume. • We prove a volume hierarchy theorem for randomized complexity: Among problems with (near) linear deterministic volume complexity, there are infinitely many distinct randomized volume complexity classes between Ω(log n) and O(n). Moreover, this hierarchy persists even when restricting to problems whose randomized and deterministic distance complexities are Θ(log n). • Similar hierarchies exist for polynomial distance complexities: we show that for any k, ℓ ∈ N with k ≤ ℓ, there are problems whose randomized and deterministic distance complexities are Θ(n1/ℓ), randomized volume complexities are [EQUATION], and whose deterministic volume complexities are [EQUATION]. We also consider connections between our volume model and massively parallel computation (MPC). We give a general simulation argument that any volume-efficient algorithm can be transformed into a space-efficient MPC algorithm.

Original languageEnglish
Title of host publicationPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
PublisherACM
Pages89-98
Number of pages10
ISBN (Electronic)9781450375825
DOIs
Publication statusPublished - 31 Jul 2020
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Virtual, Online, Italy
Duration: 3 Aug 20207 Aug 2020
Conference number: 39

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryItaly
CityVirtual, Online
Period03/08/202007/08/2020

Keywords

  • hierarchy
  • LCL
  • LOCAL model
  • locally checkable labeling
  • query complexity
  • volume complexity

Fingerprint Dive into the research topics of 'Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems'. Together they form a unique fingerprint.

Cite this