TY - GEN

T1 - Trace reconstruction with varying deletion probabilities

AU - Hartung, Lisa

AU - Holden, Nina

AU - Peres, Yuval

N1 - Publisher Copyright:
Copyright © 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - In the trace reconstruction problem an unknown string x = (x0, . . ., xn−1) ∈ {0, 1, ..., m − 1}n is observed through the deletion channel, which deletes each xk with a certain probability, yielding a contracted string X . Earlier works have proved that if each xk is deleted with the same probability q ∈ [0, 1), then exp(O(n1/3)) independent copies of the contracted string X suffice to reconstruct x with high probability. We extend this upper bound to the setting where the deletion probabilities vary, assuming certain regularity conditions. First we consider the case where xk is deleted with some known probability qk. Then we consider the case where each letter ζ ∈ {0, 1, ..., m − 1} is associated with some possibly unknown deletion probability qζ.

AB - In the trace reconstruction problem an unknown string x = (x0, . . ., xn−1) ∈ {0, 1, ..., m − 1}n is observed through the deletion channel, which deletes each xk with a certain probability, yielding a contracted string X . Earlier works have proved that if each xk is deleted with the same probability q ∈ [0, 1), then exp(O(n1/3)) independent copies of the contracted string X suffice to reconstruct x with high probability. We extend this upper bound to the setting where the deletion probabilities vary, assuming certain regularity conditions. First we consider the case where xk is deleted with some known probability qk. Then we consider the case where each letter ζ ∈ {0, 1, ..., m − 1} is associated with some possibly unknown deletion probability qζ.

UR - http://www.scopus.com/inward/record.url?scp=85043395532&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043395532&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975062.6

DO - 10.1137/1.9781611975062.6

M3 - Conference contribution

AN - SCOPUS:85043395532

T3 - 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

SP - 54

EP - 61

BT - 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

A2 - Nebel, Markus

A2 - Wagner, Stephan

PB - Society for Industrial and Applied Mathematics Publications

T2 - 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

Y2 - 8 January 2018 through 9 January 2018

ER -