Polynomial-time trace reconstruction in the smoothed complexity model

In the trace reconstruction problem, an unknown source string x ∈ {0, 1}n is sent through a probabilistic deletion channel which independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x. The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting where x may be an arbitrary string in {0, 1}n [6, 19, 7, 8, 4] and in the average-case setting where x is drawn uniformly at random from {0, 1}n [21, 9, 8, 4].