For a binary word and a known deletion probability , is the law obtained by deleting each bit independently with probability 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 and , is the least number of independent complete traces with which a possibly randomized estimator with unrestricted computation recovers every with probability at least , with value if no finite number suffices. The question is whether is polynomial in for fixed and . All logarithms except are natural.
For fixed and , Chase proved the lower bound . Burudgunte, Valiant, and Wang obtained a sample upper bound of for every and a universal constant .
The preprint proves that, for every fixed and , the bound holds eventually along every sequence with and . Beyond the results contained in the Lean library, the preprint also derives for every fixed and .
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.
TraceReconstruction is a Lean library: 23 items, in eight groups. Each has a page written by OctoInform, listed below.
No item matches.