Metraipolis › archive › dc_c32a0202fa06

Deck Reconstruction for Restricted Word Classes — arXiv:2610.41110

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41110
License (as archived)
CC0-1.0
Archived
2026-11-03T05:44:28.002Z
SHA-256 of the archived text
652ba6c70e674e0e1d8be68b1c17a91db9b0655c8d9bedd41a767f0485a8c494
Stable URL of this page
https://metraipolis.com/documento/dc_c32a0202fa06

How to cite

Deck Reconstruction for Restricted Word Classes — arXiv:2610.41110 — arXiv (en), https://arxiv.org/abs/2610.41110 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c32a0202fa06 (Metraipolis archive dc_c32a0202fa06, sha256 652ba6c70e674e0e1d8be68b1c17a91db9b0655c8d9bedd41a767f0485a8c494)
BibTeX
@misc{dcc32a0202fa06,
  title = {Deck Reconstruction for Restricted Word Classes — arXiv:2610.41110},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41110},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c32a0202fa06; sha256 652ba6c70e674e0e1d8be68b1c17a91db9b0655c8d9bedd41a767f0485a8c494},
  year = {2026}
}

Archived text

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

For a binary word $x\in \{0,1\}^+$, the $k$-deck of $x$ is the multiset of all length-$k$ subsequences counted with multiplicity. The deck reconstruction problem asks for the minimum $k$ such that every word of a fixed length is uniquely determined by its $k$-deck. In this paper, we study deck reconstruction for several restricted classes of binary words, including words with exactly $s$ ones, words with at most $\ell$ runs of ones, and words where the indices of ones are given by a monotone polynomial of degree $d$. We prove that for these classes of words, their reconstruction thresholds are bounded by a function of the structural complexity of the class. We also study weak deck reconstruction, in which subwords may contain "wildcard" symbols that map to either 0 or 1. By generalizing a "template lemma" of Dudík and Schulman, we improve the upper bound in an open question about weak reconstruction from Dudík and Schulman. Finally, for the class of periodic words with period $d$, we prove that its in-class reconstruction threshold is equal to the general reconstruction threshold for words of length $d$, and give a general template construction producing further classes with the same threshold-preservation phenomenon.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41110 — 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-11-03T05:32:16.985Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).