A Survey on Trace Reconstruction
In the trace reconstruction problem, there is an unknown binary string, and we observe noisy samples of this string after it has gone through a deletion channel. This deletion channel independently deletes each bit with constant probability q and concatenates the remaining bits. The goal is to learn the original string with high probability using as few traces as possible, where the sample complexity is characterized by the length of the string, n.
Researchers are stuck at bridging the gap between the exponential upper bound and polynomial lower bound. In the first part of this talk, I will explain the string trace reconstruction problem and the current best upper bound techniques. In the latter part, I will discuss several generalizations and variants of trace reconstruction, including our work on approximate trace reconstruction, which asks for a string “close” to the original unknown string with high probability.
Some of this talk is based on joint work with Miklos Z. Racz, Cyrus Rashtchian, and Benjamin G. Schiffer.