Project

The transmission capacity of a channel with deletions seems much harder than one with errors or erasures.  The problem appears to be one of synchronization.  See the survey article by Mitzenmacher.  Previously to Peres-Zhai (2017) information upper and lower bounds were extremely poor.  Peres-Zhai were the first to prove sub-polynomial bounds on the number of independent traces needed for reconstruction in any regime.  The goal of the present paper is use the Peres-Zhai methodology, together with a new two-step synchronization approach, to prove subpolynomial bounds at all levels of deletions. 

Problems

 One big problem is what happens in the worst case.  See Problem #7 on the list at the bottom of the main page.

Papers

Holden, N., Pemantle, R. and Peres, Y. (2017).  Subpolynomial trace reconstruction for random strings and arbitrary deletion probabilities

References

Peres, Y. and Zhai, A. (2017). Average case reconstruction for the deletion channel: sub-polynomially many traces suffice.  arXiv 1708.00854 .

Mitzenmacher, M. (2001).   A survey of results for deletion channels and related synchronization channels.