Pith. sign in

REVIEW 2 cited by

Non-Local Probes Do Not Help with Graph Problems

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1512.05411 v1 pith:M4X4UYZF submitted 2015-12-16 cs.DS

Mika Göös , Juho Hirvonen , Reut Levi , Moti Medina , Jukka Suomela This is my paper · ORCID
classification cs.DS
keywords algorithmscentraliseddistributedgraphlocalcomputingefficienthelp
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: for example, efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms

    cs.DC 2026-07 accept novelty 7.0 of 10

    Stacking of Rosenbaum–Suomela base LCLs yields LCLs of randomized VOLUME/LCA probe complexity Θ(log^k n) and ˜Θ(n^{p/q}) on bounded-degree graphs and trees.

  2. Locally computing edge orientations

    cs.DS 2025-01 conditional novelty 6.0 of 10

    First local-computation-algorithm treatment of low-out-degree edge orientation, with a Ω(√n/r) lower bound on forests and sublinear r-orientation and 4-coloring algorithms for bounded-degree forests.

Pith tools