Improved Algorithms for Population Recovery from the Deletion Channel
Shyam Narayanan · Society for Industrial and Applied Mathematics eBooks · 2021
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. Ban et al. showed how to learn ℓ-sparse distributions over strings using exp (n1/2 · (log n)O(ℓ)) samples. In this work, we learn the distribution using only exp (Õ(n1/3) · ℓ2) samples, by developing a higher-moment analog of the algorithms of [DOS17a, NP17], which solve trace reconstruction in exp (Õ(n1/3)) samples. We also give the first algorithm with a runtime subexponential in n, solving population recovery in exp (Õ(n1/3) · ℓ3) samples and time. Notably, our dependence on n nearly matches the upper bound of [DOS17a, NP17] when ℓ = O(1), and we reduce the dependence on ℓ from doubly to singly exponential. Therefore, we are able to learn large mixtures of strings: while Ban et al.'s algorithm can only learn a mixture of O(log n/ log log n) strings with a subexponential number of samples, we are able to learn a mixture of no(1) strings in exp (n1/3+o(1)) samples and time.