Deck Reconstruction for Restricted Word Classes

Krishna Angal, Ruben Ascoli, Simon X. He, Xiaoyu He, Logan Post, Arker Oke Soe, Olga Zhukova

arXivarxiv/2610.41110Oct 30, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.41110
curl -X POST /api/v1/records/arxiv/2610.41110/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.41110/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'