Beyond trace reconstruction: Population recovery from the deletion channel
share
Population recovery is the problem of learning an unknown distribution over an unknown set of n-bit strings, given access to independent draws from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the bit-flip and erasure noise channels. We initiate the study of population recovery under the deletion channel, in which each bit is independently deleted with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip noise or erasure noise; indeed, even the simplest case in which the population size is 1 (corresponding to a trivial distribution supported on a single string) corresponds to the trace reconstruction problem, a challenging problem that has received much recent attention (see e.g. DOS17,NP17,PZ17,HPP18,HHP18). We give algorithms and lower bounds for population recovery under the deletion channel when the population size is some ℓ>1. As our main sample complexity upper bound, we show that for any ℓ=o( n/ n), a population of ℓ strings from {0,1}^n can be learned under deletion channel noise using 2^n^1/2+o(1) samples. On the lower bound side, we show that n^Ω(ℓ) samples are required to perform population recovery under the deletion channel, for all ℓ≤ n^1/2-ϵ. Our upper bounds are obtained via a robust multivariate generalization of a polynomial-based analysis, due to Krasikov and Roddity KR97, of how the k-deck of a bit-string uniquely identifies the string; this is a very different approach from recent algorithms for trace reconstruction (the ℓ=1 case). Our lower bounds build on moment-matching results of Roos Roo00 and Daskalakis and Papadimitriou DP15.
READ FULL TEXT