Trace Reconstruction for Deletion Channels
- Yuval Peres
- Joint work with Nina Holden, Fedor Nazarov, Robin Pemantle, and Alex Zhai
12/06/2020
Date
102
Slides
Previous
Next
Useful Information
- Article: Nazarov, Fedor, and Yuval Peres. "Trace reconstruction with exp (O (n1/3)) samples." In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1042-1046. 2017.
- Article: Holden, Nina, Robin Pemantle, and Yuval Peres. "Subpolynomial trace reconstruction for random strings\{and arbitrary deletion probability." In Conference On Learning Theory, pp. 1799-1840. PMLR, 2018.
- Article: Peres, Yuval, and Alex Zhai. "Average-case reconstruction for the deletion channel: subpolynomially many traces suffice." In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 228-239. IEEE, 2017.
- Article: Hartung, Lisa, Nina Holden, and Yuval Peres. "Trace reconstruction with varying deletion probabilities." In 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 54-61. Society for Industrial and Applied Mathematics, 2018.
- Related video: Trace reconstruction for deletion channels - TCS+ :Theory of Computing online lecture