Improved Algorithms for Population Recovery from the Deletion Channel

Understand

The population recovery problem asks one to recover an unknown distribution over $n$-bit strings given access to independent noisy samples of strings drawn from the distribution.

• Recently, Ban et al.
• [BCF+19] studied the problem where the noise is induced through the deletion channel.
• This problem generalizes the famous trace reconstruction problem, where one wishes to learn a single string under the deletion channel.