Shotgun Assembly of the Non-Uniform Labeled Lattice Model
Abstract
In this paper, we study the graph shotgun assembly problem in the labeled lattice model, as introduced by Mossel and Ross (2019). We start with a d-dimensional lattice of length n, where the color of each vertex is sampled i.i.d. from a distribution π. Then, we ask whether it is possible to reconstruct the coloring of the lattice given the coloring of each subgrid of length k. While previous work by Ding and Liu (2023) and Demidovich, Panichkin, and Zhukovskii (2023) identified the reconstruction threshold when π is uniform, we examine the non-uniform case. This paper establishes a sufficient condition for the impossibility of reconstruction for d ≥ 2 using information-theoretic arguments. Our negative result matches the known threshold in the uniform case.
Related
- Mesh-Uniform Power Stability of Two-Relaxation-Time Vector Lattice Boltzmann Schemes with Reversible Boundaries
- A uniform elliptic reduction, an order-matching criterion, and precision benchmarks for the strong-coupling Birman-Schwinger analysis of the lattice three-boson trimer
- Randomly shifted lattice rules for SDEs with constant diffusion: error bounds uniform in time discretization and dimension
- Maximal Order Type and Width of the h-Preorder on Finite Labeled Trees
- Full immersions in Eulerian group-labeled graphs
BibTeX
@misc{gaudio2026shotgun,
title = {{Shotgun Assembly of the Non-Uniform Labeled Lattice Model}},
author = {Julia Gaudio and Charlie K. Guan and Andrew Jin},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05532},
eprint = {2611.05532},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05532},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Shotgun Assembly of the Non-Uniform Labeled Lattice Model
AU - Julia Gaudio
AU - Charlie K. Guan
AU - Andrew Jin
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05532
UR - https://arxiv.org/abs/2611.05532
AB - In this paper, we study the graph shotgun assembly problem in the labeled lattice model, as introduced by Mossel and Ross (2019). We start with a d-dimensional lattice of length n, where the color of each vertex is sampled i.i.d. from a distribution π. Then, we ask whether it is possible to reconstruct the coloring of the lattice given the coloring of each subgrid of length k. While previous work by Ding and Liu (2023) and Demidovich, Panichkin, and Zhukovskii (2023) identified the reconstruction threshold when π is uniform, we examine the non-uniform case. This paper establishes a sufficient condition for the impossibility of reconstruction for d ≥ 2 using information-theoretic arguments. Our negative result matches the known threshold in the uniform case.
ER -