Beyond trace reconstruction: Population recovery from the deletion channel (Xi Chen)

Abstract

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 corrupted according to some noise channel. We study the problem under the deletion channel, in which each bit is independently deleted and the surviving bits are concatenated. This is a more challenging noise model than bit-flip or erasure noise; indeed, even the simplest case in which the population is of size 1 corresponds to the trace reconstruction problem, for which an exponential gap remains in the sample complexity.

In this talk we review recent results for trace reconstruction and present newupper and lower bounds for the sample complexity of population recoveryunder the deletion channel.

Based on joint work with Frank Ban (Berkeley), Adam Freilich, Rocco A. Servedio and Sandip Sinha (Columbia).

Time

Speaker

Room