Average-case reconstruction for the deletion channel: subpolynomially many traces suffice

2017/08/01 by Peres, Yuval, Zhai, Alex · 1 citation
#62B10 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)

paper · doi:10.48550/arxiv.1708.00854

Abstract

The deletion channel takes as input a bit string x ∈ \0,1\ⁿ, and deletes each bit independently with probability q, yielding a shorter string. The trace reconstruction problem is to recover an unknown string x from many independent outputs (called "traces") of the deletion channel applied to x. We show that if x is drawn uniformly at random and q < 1/2, then e^O(log^1/2 n) traces suffice to reconstruct x with high probability. The previous best bound, established in 2008 by Holenstein-Mitzenmacher-Panigrahy-Wieder, uses n^O(1) traces and only applies for q less than a smaller threshold (it seems that q < 0.07 is needed). Our algorithm combines several ideas: 1) an alignment scheme for "greedily" fitting the output of the deletion channel as a subsequence of the input; 2) a version of the idea of "anchoring" used by Holenstein-Mitzenmacher-Panigrahy-Wieder; and 3) complex analysis techniques from recent work of Nazarov-Peres and De-O'Donnell-Servedio.

Cited by

• New Bounds for Circular Trace Reconstruction

Related

• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem
• Polynomial-time trace reconstruction in the low deletion rate regime
• Approximate Trace Reconstruction from a Single Trace
• Beyond trace reconstruction: Population recovery from the deletion channel