Pith Number

pith:3PWW4YR7

pith:2026:3PWW4YR753Q4QDTFUKES2YYRQE

not attested not anchored not stored refs resolved

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size

Alkida Balliu, Dennis Olivetti, Fabian Kuhn, Gustav Schmid, Sebastian Brandt, Timoth\'e Picavet

The complexity of LCLs on trees changes when nodes lack exact knowledge of network size n.

arxiv:2605.12787 v1 · 2026-05-12 · cs.DC · cs.CC

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{3PWW4YR753Q4QDTFUKES2YYRQE}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

If nodes are oblivious to n, or know only a polynomial upper bound on it, then even on trees, the theory of LCLs changes significantly: randomness helps in more cases; some problems have very unnatural complexities; and some have a lower bound that depends on which definition of Ω we use!

C2weakest assumption

That the prior classifications of LCL complexity on trees, which relied on nodes knowing n, can be directly compared or extended without re-deriving the entire landscape under the new knowledge assumptions.

C3one line summary

Knowledge of network size n alters the distributed complexity of LCL problems on trees, making randomness useful in more cases and creating unnatural complexity classes.

References

35 extracted · 35 resolved · 0 Pith anchors

[1] Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms 2023

[2] The distributed complexity of locally checkable problems on paths is decidable 2019

[3] Effi- cient classification of locally checkable problems in regular trees 2022

[4] Classification of distributed binary labeling problems 2020

[5] Exponential speedup over locality in MPC with optimal memory 2022

Formal links

2 machine-checked theorem links

Cited by

1 paper in Pith

Meta-Theorems for Cuttable Distributed Problems

Receipt and verification

First computed	2026-05-18T03:09:13.010336Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

dbed6e623feee1c80e65a2892d63118139caa72395e743fcaf7ca61692cbae33

Aliases

arxiv: 2605.12787 · arxiv_version: 2605.12787v1 · doi: 10.48550/arxiv.2605.12787 · pith_short_12: 3PWW4YR753Q4 · pith_short_16: 3PWW4YR753Q4QDTF · pith_short_8: 3PWW4YR7

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/3PWW4YR753Q4QDTFUKES2YYRQE \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: dbed6e623feee1c80e65a2892d63118139caa72395e743fcaf7ca61692cbae33

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "4a8b727b09f7809da3db20732dab69abbab2252ab1eb1c08728f62b8e7e3085d",
    "cross_cats_sorted": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DC",
    "submitted_at": "2026-05-12T22:02:21Z",
    "title_canon_sha256": "cf806363e2b0a63f0582bd7d0592b931ea7e4090373e1e6d2ac319190273dab6"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.12787",
    "kind": "arxiv",
    "version": 1
  }
}