Polynomial-time trace reconstruction in the low deletion rate regime
summary
Claim: a polynomial-time algorithm reconstructs any n-bit string with high probability using polynomially many traces when the deletion rate δ < n^{-1/3+ε}. Technique: alternate piecewise majority alignment (BMA) to recover blocks up to a repeated-pattern “desert” and a find-end routine that locates desert endpoints and aligns fresh traces via a small signature subword. Key parameter: interval length σ ≈ sqrt(δ n log n) and requirement σ << 1/δ forces the n^{-1/3} barrier. Sampling and runtime are polynomial; removing the barrier remains open.
AI-written summary · about