Seminars

View all Seminars  |  Download ICal for this event

Beyond trace reconstruction: Population recovery from the deletion channel

Series: Theory Seminar Series

Speaker: Sandip Sinha Ph.D Student CS Theory Group Columbia University

Date/Time: Nov 27 04:41:46

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Faculty Advisor:

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 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

Speaker Bio:
Bio: Sandip Sinha is a Ph.D student in the CS theory group at Columbia University. He is advised by Profs. Rocco Servedio, Alex Andoni, and Cliff Stein. His primary interest is in computational learning theory, as well as data structures for various problems on strings. He is also interested in sublinear algorithms. Before joining Columbia, he graduated from the Indian Institute of Science (IISc) with a B.S. degree in Mathematics in 2016.

Host Faculty: Dr. Arindam Khan