Abstract
Alice has a length n binary string x. She transmits it to Bob over a deletion channel that deletes each bit with probability 1/2. How many transmissions of x are necessary before Bob can reconstruct x with high probability? This problem is known as the trace reconstruction problem. The problem has attracted significant attention over the last fourteen years but there is still a big gap between the best known lower and upper bounds. The goal of our work in to understand the complexity of the problem in terms of parameters such as the sparsity and run lengths of the transmitted string.