The population recovery problem asks one to recover an unknown distribution over n-bit strings given query access to independent noisy samples of strings drawn from the distribution. Recently, Ban et . al. [BCF+19] studied the problem where the unknown distribution over n-bit strings is known to be \ell-sparse for some fixed \ell, and the noise is induced through the deletion channel. The deletion channel is a noise model where each bit of the string is independently deleted with some fixed probability, and the retained bits are concatenated. We note that if \ell = 1, i.e., we are trying to learn a single string , learning the distribution is equivalent to the famous trace reconstruction problem. The best known algorithms for trace reconstruction require \exp%DIFDELCMD < \left(%%% O(n^{1/3)}%DIFDELCMD < \right) %%% samples. For population recovery under the deletion channel , Ban et . al. provided an algorithm that could learn \ell-sparse distributions over strings using \exp %DIFDELCMD < \left(%%% \big( n^{1/2} \cdot (\log n)^{O(\ell)} %DIFDELCMD < \right) %%% \big) samples. In this work, we provide an algorithm that learns the distribution using only \exp\big(O(n^{1/3}) \cdot \ell^2\big) samples, by developing a higher-moment analog of the algorithms of [DOS17, NP17] \big(O)}\big)  . We also give the first algorithm with a runtime subexponential in n, which solves population recovery in \exp\big(\tilde{O}(n^{1/3}) \cdot \ell^3\big) samples and time. Notably, our dependence on n nearly matches the known upper bound  when \ell =  1  , and we reduce the dependence on \ell from doubly to nearly singly exponential. Therefore, we are able to learn the mixture even for much larger values of \ell. For instance, Ban et . al.'s algorithm can only learn a mixture of O(\log n/\log \log n) strings with a subexponential number of queries, whereas we are able to learn a mixture of up to n^{o(1)} strings in subexponential queries\big(}\big)  and time.
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 %DIFDELCMD < \left(%%% )}%DIFDELCMD < \right) %%% under the deletion channel . Ban et al. showed how to learn \ell-sparse distributions over strings using \exp %DIFDELCMD < \left(%%% \big( n^{1/2} \cdot (\log n)^{O(\ell)} %DIFDELCMD < \right) %%% \big) samples. In this work, we learn the distribution using only \exp\big(O(n^{1/3}) \cdot \ell^2\big) samples, by developing a higher-moment analog of the algorithms of [DOS17, NP17] , which solve trace reconstruction in \exp\big(O(n^{1/3)}\big) samples . We also give the first algorithm with a runtime subexponential in n, solving population recovery in \exp\big(\tilde{O}(n^{1/3}) \cdot \ell^3\big) samples and time. Notably, our dependence on n nearly matches the upper bound of DOS17, NP17 when \ell = O( 1 ) , and we reduce the dependence on \ell 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 n^{o(1)} strings in \exp\big(n^{1/3 + o(1)}\big) samples and time.
D
query
D
.
D
unknown distribution over n-bit strings is known to be \ell-sparse for some fixed \ell, and the
R
The deletion channel is a noise model where each bit of the string is independently deleted with some fixed probability, and the retained bits are concatenated. We note that if \ell = 1, i.e., we are trying
This problem generalizes the famous trace reconstruction problem, where one wishes
D
, learning the distribution is equivalent to the famous trace reconstruction problem. The best known algorithms for trace reconstruction require \exp
D
O(n^{1/3
D
samples. For population recovery
R
, Ban et . al. provided an algorithm that could
. Ban et al. showed how to
R
provide an algorithm that learns
learn
A
, which solve trace reconstruction in \exp
A
(n^{1/3
A
samples
R
which solves
solving
R
known upper bound
upper bound of
A
DOS17, NP17
A
O(
A
)
D
nearly
R
the mixture even for much larger values of \ell. For instance, Ban et .
large mixtures of strings: while Ban et
R
queries, whereas
samples,
D
up to
R
subexponential queries
\exp
A
n^{1/3 + o(1)
A
samples