Pith Number

pith:B6PYU6UD

pith:2026:B6PYU6UDGY54PCKUDPLMWV2GZ5

not attested not anchored not stored refs resolved

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs

David Tench, Gilvir Gill, Laxman Dhulipala, Michael A. Bender, Quinten De Man

Hybrid sketching algorithms achieve dynamic connectivity space that matches the best of lossless and sketch-based methods on all graph densities.

arxiv:2605.15173 v1 · 2026-05-14 · cs.DS · cs.DB

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{B6PYU6UDGY54PCKUDPLMWV2GZ5}

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

We design new hybrid algorithms for fully-dynamic and semi-streaming connectivity with space O(min{V+E, V log V log(2+E/V)}) w.h.p., simultaneously matching the lossless bound on sparse graphs, the sketching bound on dense graphs, and improving on both in an intermediate regime.

C2weakest assumption

Real-world sparse graphs contain dense cores on a small subset of vertices that account for a large fraction of edges, so that sketching only the core yields net space savings.

C3one line summary

Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.

References

66 extracted · 66 resolved · 3 Pith anchors

[1] Acar, Daniel Anderson, Guy E 2019 · doi:10.1145/3323165.3323196

[2] Acar, Daniel Anderson, Guy E 2020 · doi:10.4230/lipics.esa.2020.2

[3] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Analyzing graph structure via linear measurements. InProceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 459– 2012

[4] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Graph sketches: sparsification, spanners, and subgraphs. InPODS. ACM, 5–14 2012

[5] The Space Complexity of Approximating the Frequency Moments , journal = 1999 · doi:10.1006/jcss.1997.1545

Formal links

1 machine-checked theorem link

Receipt and verification

First computed	2026-05-17T21:40:25.267253Z
Last reissued	2026-05-17T21:57:18.606266Z
Builder	pith-number-builder-2026-05-17-v1
Signature	unsigned_v0
Schema	pith-number/v1.0

Canonical hash

0f9f8a7a83363bc789541bd6cb5746cf746473ed6570c4036829881ebe6c0ec4

Aliases

arxiv: 2605.15173 · arxiv_version: 2605.15173v1 · pith_short_12: B6PYU6UDGY54 · pith_short_16: B6PYU6UDGY54PCKU · pith_short_8: B6PYU6UD

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/B6PYU6UDGY54PCKUDPLMWV2GZ5 \
  | 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: 0f9f8a7a83363bc789541bd6cb5746cf746473ed6570c4036829881ebe6c0ec4

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "04e7fdccff2138dbc86bcbd3fbe4fa8e346f7c2d719ceb5f23c7284f343ef15f",
    "cross_cats_sorted": [
      "cs.DB"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-14T17:57:03Z",
    "title_canon_sha256": "1e91fcd714b55617895a600c21d0c5806e6fddd2b46ec8a1d805fff6a3b03948"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.15173",
    "kind": "arxiv",
    "version": 1
  }
}