Pith Number

pith:OLZKI52B

pith:2026:OLZKI52BARBBFEJJPDAJ6XCOCK

not attested not anchored not stored refs resolved

Testing properties of trees in graphical models with covariance queries

Francisco Calvillo, G\'abor Lugosi, Piotr Zwiernik, Sofiya Burova

Global structural properties of trees in graphical models can be tested with sub-quadratic covariance queries.

arxiv:2605.15996 v1 · 2026-05-15 · stat.ML · cs.LG · math.ST · stat.TH

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{OLZKI52BARBBFEJJPDAJ6XCOCK}

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

The main results of the paper show that, while reconstructing the entire tree may be costly, certain global structural properties can be tested efficiently. In particular, we design randomized tests for global structural properties that use a sub-quadratic number of queries.

C2weakest assumption

The underlying graph is exactly a tree and the covariance query model introduced in the cited 2021 work applies directly to the testing procedures.

C3one line summary

The paper presents randomized tests with explicit query bounds for properties including number of leaves, maximum degree, typical distance, and diameter in tree-structured graphical models.

References

16 extracted · 16 resolved · 0 Pith anchors

[1] Optimization Under Unknown Constraints 2013 · doi:10.1093/acprof:oso/9780199535255.001.0001

[2] The recovery of trees from measures of dissimilarity.Mathematics in the archae- ological and historical sciences, 1971 1971

[3] Estimating sparse precision matrix: Optimal rates of convergence and adaptive estimation.The Annals of Statistics, 44(2):455–488, 2016 2016

[4] Active learning algo- rithms for graphical model selection 2016

[5] Property testing in graphical models: testing small separation numbers.Information and Inference: A Journal of the IMA, 2026, to appear 2026

Formal links

1 machine-checked theorem link

Receipt and verification

First computed	2026-05-20T00:01:48.232580Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

72f2a47741044212912978c09f5c4e12bd363bb6d4e0fb0d9b9d338cee2d7c12

Aliases

arxiv: 2605.15996 · arxiv_version: 2605.15996v1 · doi: 10.48550/arxiv.2605.15996 · pith_short_12: OLZKI52BARBB · pith_short_16: OLZKI52BARBBFEJJ · pith_short_8: OLZKI52B

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/OLZKI52BARBBFEJJPDAJ6XCOCK \
  | 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: 72f2a47741044212912978c09f5c4e12bd363bb6d4e0fb0d9b9d338cee2d7c12

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "bd86c4a0435c2e138e017708ca96e0107994737aad38da4c0e65c7d979c51cd7",
    "cross_cats_sorted": [
      "cs.LG",
      "math.ST",
      "stat.TH"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "stat.ML",
    "submitted_at": "2026-05-15T14:26:19Z",
    "title_canon_sha256": "09c53799ad3941bdc64ae345816097b3be88c972108144f1f3f9579dae0ae7b1"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.15996",
    "kind": "arxiv",
    "version": 1
  }
}