Metraipolis › archive › dc_45ba1cca7cd7

Degree Sequence Reconstruction from Subgraph Traces — arXiv:2609.09397

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09397
License (as archived)
CC0-1.0
Archived
2026-10-16T10:53:17.606Z
SHA-256 of the archived text
d8b7d53e85b2df35bd83282b6a8a86ca3d354f3e10a9282716f8c610f8cd885d
Stable URL of this page
https://metraipolis.com/documento/dc_45ba1cca7cd7

How to cite

Degree Sequence Reconstruction from Subgraph Traces — arXiv:2609.09397 — arXiv (en), https://arxiv.org/abs/2609.09397 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_45ba1cca7cd7 (Metraipolis archive dc_45ba1cca7cd7, sha256 d8b7d53e85b2df35bd83282b6a8a86ca3d354f3e10a9282716f8c610f8cd885d)
BibTeX
@misc{dc45ba1cca7cd7,
  title = {Degree Sequence Reconstruction from Subgraph Traces — arXiv:2609.09397},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09397},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_45ba1cca7cd7; sha256 d8b7d53e85b2df35bd83282b6a8a86ca3d354f3e10a9282716f8c610f8cd885d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09397. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The goal of degree sequence reconstruction is to recover the ordered vector of degrees of an unknown graph from vertex deleted traces, where each vertex is deleted independently with probability $p$. We provide two algorithms for reconstruction; the first uses rejection sampling to reduce the problem to an estimation problem for a mixture distribution. Combined with prior trace reconstruction results, this gives a reconstruction algorithm using $\Exp{\tilde O (n^{1/3})}$ traces, although no sub-exponential time decoder is known. Our other approach involves recovering certain graph invariants, degree moments, that can identify a graphs degree sequence. Extremal polynomial bounds show that $\tilde \Theta(n^{1/2})$ degree moments are necessary and sufficient to reconstruct the degree sequence, which leads to an algorithm with $\Exp{\tilde O(n^{1/2})}$ trace complexity. The same polynomial machinery yields a sub-exponential time decoder for the degree sequence from the moments. Additionally, we give an $O(n^{3})$ upper bound and a $\Omega(n^2)$ lower bound for the trace complexity of recovering the number of edges.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.09397 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T09:00:25.834Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).