Dudík–Schulman weak deck-reconstruction problem
For and , let denote the multiset of all length- subsequences of a word , counted with multiplicity. Define to be the least such that implies for all . Determine , or equivalently determine the asymptotic growth of the minimum subsequence length required to reconstruct every binary word of length from its -deck.
References
- Deck Reconstruction for Restricted Word Classes — arXiv — Krishna Angal, Ruben Ascoli, Simon X. He, Xiaoyu He, Logan Post, Arker Oke Soe, Olga Zhukova
Source: arXiv
Progress summary
A July 2026 paper reports better bounds for several restricted cases, but the general reconstruction question remains open.
The Dudík–Schulman question asks how much subsequence data is needed to distinguish binary words. The general problem remains unresolved.
Known results
- Dudík and Schulman’s earlier bound was reported as .
- For the general threshold , the known bounds remain ; the true asymptotic behavior is unknown.
July 2026 restricted-word bounds
Krishna Angal, Ruben Ascoli, Simon X. He, Xiaoyu He, Logan Post, Arker Oke Soe, and Olga Zhukova report a generalized template lemma giving, as and , . They also obtain results for sparse, low-run, polynomial-index, and periodic words, answering parts of the open questions without resolving the general case. The preprint’s mathematical claims are unverified.
Current status (as of November 2026): A preprint claims improved bounds and several structured-case results, while the general Dudík–Schulman problem remains open and the claims are unverified.
Sources
Solutions 0
No solutions have been posted yet.