English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

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

Rosenbaum, W., & Suomela, J. (2020). Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems. Retrieved from https://arxiv.org/abs/1907.08160.

Item is

Basic

show hide
Genre: Paper
Latex : Seeing Far vs. Seeing Wide: {V}olume Complexity of Local Graph Problems

Files

show Files
hide Files
:
arXiv:1907.08160.pdf (Preprint), 9KB
Name:
arXiv:1907.08160.pdf
Description:
File downloaded from arXiv at 2020-12-17 15:27
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/xhtml+xml / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Rosenbaum, Will1, Author           
Suomela, Jukka2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
 Abstract: Consider 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 solution each node needs to
explore the input graph at least up to distance $\Omega(\log n)$ in order to
produce its output. We consider the complexity of such problems from the
perspective of volume: how large a subgraph does a node need to see in order to
produce its output. We study locally checkable graph problems on bounded-degree
graphs. We give a number of constructions that exhibit 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. In contrast, we show that there are problems with
linear deterministic volume but only logarithmic randomized volume.
- We prove a volume hierarchy theorem for randomized complexity: among
problems with linear deterministic volume complexity, there are infinitely many
distinct randomized volume complexity classes between $\Omega(\log n)$ and
$O(n)$. This hierarchy persists even when restricting to problems whose
randomized and deterministic distance complexities are $\Theta(\log n)$.
- Similar hierarchies exist for polynomial distance complexities: for any $k,
\ell \in N$ with $k \leq \ell$, there are problems whose randomized and
deterministic distance complexities are $\Theta(n^{1/\ell})$, randomized volume
complexities are $\Theta(n^{1/k})$, and whose deterministic volume complexities
are $\Theta(n)$.
Additionally, we 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.

Details

show
hide
Language(s): eng - English
 Dates: 2019-07-182020-02-172020
 Publication Status: Published online
 Pages: 44 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1907.08160
BibTex Citekey: Rosenbaum_arXiv1907.08160
URI: https://arxiv.org/abs/1907.08160
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show