Approximate trace reconstruction of random strings from a constant number of traces

Abstract: In the trace reconstruction problem, the goal is to reconstruct an unknown string

x

of length

n

from multiple traces obtained by passing

x

through the deletion channel. In the relaxed problem of

a p p r o x i m a t e

trace reconstruction, the goal is to reconstruct an approximation

w i d e h a t x

of

x

which is close (within

e p s i l o n n

) to

x

in edit distance. We show that for most strings

x

, this is possible with high probability using only a constant number of traces. Crucially, this constant does not grow with

n

, and only depends on the deletion probability and

e p s i l o n

.

This page was built for publication: Approximate trace reconstruction of random strings from a constant number of traces