← All problems

Dudík–Schulman weak deck-reconstruction problem

For n≥1n\ge 1 and 0≤k≤n0\le k\le n, let Dk(x)D_k(x) denote the multiset of all length-kk subsequences of a word x∈{0,1}nx\in\{0,1\}^n, counted with multiplicity. Define r(n)r(n) to be the least kk such that Dk(x)=Dk(y)D_k(x)=D_k(y) implies x=yx=y for all x,y∈{0,1}nx,y\in\{0,1\}^n. Determine r(n)r(n), or equivalently determine the asymptotic growth of the minimum subsequence length required to reconstruct every binary word of length nn from its kk-deck.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 Ot(kt+1log⁡k)O_t(k^{t+1}\log k).
  • For the general threshold r(n)r(n), the known bounds remain eΩ(log⁡n)≤r(n)≤O(n)e^{\Omega(\sqrt{\log n})}\le r(n)\le O(\sqrt n); 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 k→∞k\to\infty and 0≤t≤k0\le t\le k, S(k,t)≤k3log⁡3log⁡(t+1)+O(log⁡log⁡k)S(k,t)\le k^{\frac{3}{\log 3}\log(t+1)+O(\log\log k)}. 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.