Robust Reconstruction on Trees with a Growing Alphabet

Abstract

We study robust reconstruction for the q-state Potts broadcast process on a Galton-Watson tree in the growing-alphabet regime q→∞, with boundary depth growing sufficiently quickly in relation to q. We show that, in the regime dλ>1, where d is the expected number of offspring and λ is the nontrivial eigenvalue of the Potts transition matrix, the root posterior is asymptotically unchanged by a broad class of noise channels applied independently to the boundary labels. This remains true even when the probability of retaining the true label at an individual boundary vertex tends to zero as q→∞. More precisely, under suitable moment and noise assumptions, the noiseless and noisy root posteriors converge to one another in expected total variation, and hence have the same asymptotic Bayes-optimal reconstruction accuracy.

Robust and Learned Online Matching in Growing Trees
Marek Gałązka, Hanna Wdowicka
arXiv30 Sep 2026PreprintCC BY 4.0Full textProbabilityarXiv
First-Derivative Chromatic Symmetric Reconstruction For Proper Trees
Saad A. Awan
arXiv29 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Largest Rashomon sets of decision trees for robust contextual optimization
Lorenzo Bonasera, David Pisinger
arXiv3 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
The pressure-robust virtual element methods with reconstruction for the Stokes equation
Jikun Zhao, Wenhao Zhu, Zhaonan Dong +1
HAL7 Sep 2026PreprintCC BY 4.0Full textGeneral mathematicsHAL
When Lower Reconstruction Loss Hurts: Distributionally Robust Refinement for Low-Bit LLM Quantization
Yanlong Zhao, Xiaoyuan Cheng, Huihang Liu +6
arXiv8 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{lee2026robust,
  title = {{Robust Reconstruction on Trees with a Growing Alphabet}},
  author = {Heon Lee},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33263},
  eprint = {2609.33263},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33263},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Robust Reconstruction on Trees with a Growing Alphabet
AU  - Heon Lee
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33263
UR  - https://arxiv.org/abs/2609.33263
AB  - We study robust reconstruction for the q-state Potts broadcast process on a Galton-Watson tree in the growing-alphabet regime q→∞, with boundary depth growing sufficiently quickly in relation to q. We show that, in the regime dλ>1, where d is the expected number of offspring and λ is the nontrivial eigenvalue of the Potts transition matrix, the root posterior is asymptotically unchanged by a broad class of noise channels applied independently to the boundary labels. This remains true even when the probability of retaining the true label at an individual boundary vertex tends to zero as q→∞. More precisely, under suitable moment and noise assumptions, the noiseless and noisy root posteriors converge to one another in expected total variation, and hence have the same asymptotic Bayes-optimal reconstruction accuracy.
ER  -

Abstract

Related

Cite