BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20200106T120000Z
UID:d2189ece54acb242774fcf34f7694b7b-33
DTSTAMP:19700101T120013Z
DESCRIPTION:Beyond trace reconstruction: Population recovery from the deletion channel
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/33/beyond-trace-reconstruction-population-recovery-from-the-deletion-channel/
SUMMARY: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, in both worst-case and average-case settings of the strings in the support. This is a generalization of trace reconstruction, a challenging problem that has received much recent attention. 
For the worst case, we show that for any s = o(log n / log log n), a population of s strings from {0,1}^n can be learned under deletion channel noise using exp(n^{1/2+o(1)}) samples. On the lower bound side, we show that n^{Omega(s)} samples are required to perform population recovery under the deletion channel, for all s <= n^0.49.

For the average case, we give an efficient algorithm for population recovery. The algorithm runs in time poly(n,s,1/eps) and its sample complexity is poly(s, 1/eps, exp(log^{1/3} n)), where eps is the TV distance between the original and output distributions.

This is based on the following joint work with Frank Ban, Xi Chen, Adam Freilich and Rocco Servedio: https://arxiv.org/abs/1904.05532 https://arxiv.org/abs/1907.05964
DTSTART:20200106T120000Z
END:VEVENT
END:VCALENDAR