OctoInformBeta

Quantitative trace-reconstruction bounds with a uniform decoder

For a binary word xx and a known deletion probability q∈(0,1)q\in(0,1), 𝒟q(x)\mathcal D_q(x) is the law obtained by deleting each bit independently with probability qq and concatenating the surviving bits in order. A complete trace records the surviving bits and their length, without their original positions. For a positive integer nn and s∈(0,1]s\in(0,1], Tq,s(n)T_{q,s}(n) is the least number of independent complete traces with which a possibly randomized estimator with unrestricted computation recovers every x∈{0,1}nx\in\{0,1\}^n with probability at least ss, with value +∞+\infty if no finite number suffices. The question is whether Tq,s(n)T_{q,s}(n) is polynomial in nn for fixed qq and ss. All logarithms except log⁡2\log_2 are natural.

For fixed qq and s>1/2s>1/2, Chase proved the lower bound Tq,s(n)=Ω(n3/2/log⁡7n)T_{q,s}(n)=\Omega(n^{3/2}/\log^7 n). Burudgunte, Valiant, and Wang obtained a sample upper bound of exp⁡((1−q)−7/3(log⁡2n)C0)\exp((1-q)^{-7/3}(\log_2 n)^{C_0}) for every q∈(0,1)q\in(0,1) and a universal constant C0C_0.

The preprint proves that, for every fixed s∈(0,1]s\in(0,1] and 0<c<1/(4log⁡2)0<c<1/(4\log 2), the bound Tq,s(n)≥nclog⁡(q3log⁡n)T_{q,s}(n)\ge n^{c\log(q^3\log n)} holds eventually along every sequence with n→∞n\to\infty and q3log⁡n→∞q^3\log n\to\infty. Beyond the results contained in the Lean library, the preprint also derives nAmin⁡x≠y∈{0,1}nTV⁡(𝒟q(x),𝒟q(y))→0n^A\min_{x\ne y\in\{0,1\}^n}\operatorname{TV}(\mathcal D_q(x),\mathcal D_q(y))\to0 for every fixed q∈(0,1)q\in(0,1) and A>0A>0.

The Lean library contains intermediate results for trace reconstruction. Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to the declaration behind it. Where the preprint states a result differently, its statement appears beside the Lean library’s statement. The preprint is a guide only to the order and names of the results.

The Lean library: TraceReconstruction

TraceReconstruction is a Lean library: 23 items, in eight groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1: Complete traces and reconstruction Complete traces and uniform reconstruction.
  2. §1: Distances and working deletion rate Distances and deletion rates for complete traces.
§2. The induction and global scales 4 items
  1. §2: The global schedule A schedule for the multiscale construction.
  2. Lemma 2.1 Target scales absorb deletion losses uniformly.
  3. Definition 2.2 Level pairs with controlled trace simulation.
  4. Proposition 2.3 Level pairs eventually reach every scheduled scale.
§3. Common mass, smoothing, and score moments 3 items
  1. Lemma 3.1 Coefficient energy bounds multilinear even moments.
  2. Lemma 3.2 Positive trace overlap grows under sufficient repetition.
  3. Lemma 3.3 Clipping controls loss and score moments.
§4. An initial pair at the working deletion rate 5 items
  1. Proposition 4.1 Eventual initial pairs with controlled trace error.
  2. §4: Periodic defects, counted primitive marks, and rank kernels Periodic defects through their retained ranks.
  3. Lemma 4.2 A uniform estimate for periodic rank kernels.
  4. Lemma 4.3 Bounding mixed positional differences of rank kernels.
  5. Lemma 4.4 Central periods bound coarse gap sums.
§5. One amplification block: words and overlap 4 items
  1. Proposition 5.1 One block advances a trace pair.
  2. §5: Nested complementary words and windows Nested words and rounded reconstruction windows.
  3. Lemma 5.2 Prouhet convolutions admit binomial smoothing bounds.
  4. Lemma 5.3 Adjacent powers of nested atoms retain overlap.
§6. An observation with randomly displaced windows 2 items
  1. §6: The unconditioned surrogate and metadata Sampling displaced windows from their side reports.
  2. Lemma 6.1 A window oracle simulates root traces.
§7. Likelihood cancellation and the forced binary subtree 1 item
  1. Lemma 7.1 Conditional cancellation bounds signed score moments.
§8. Genuine traces, exact lengths, and testing 2 items
  1. Lemma 8.1 Restoring exact lengths with sample bounds.
  2. §8: Multiple gadgets and unrestricted testing Exact-length gadget families bound reconstruction success.

No item matches.