All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD5-S7-T4.2
Paper Title Mean-Based Trace Reconstruction over Practically any Replication-Insertion Channel
Authors Mahdi Cheraghchi, Joseph Downs, University of Michigan - Ann Arbor, United States; João Ribeiro, Imperial College London, United Kingdom; Alexandra Veliche, University of Michigan - Ann Arbor, United States
Session D5-S7-T4: Trace Reconstruction & Coding for DNA Storage
Chaired Session: Saturday, 17 July, 00:00 - 00:20
Engagement Session: Saturday, 17 July, 00:20 - 00:40
Abstract Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $\exp(O(n^{1/3}))$ traces are necessary and sufficient for mean-based worst-case trace reconstruction over the deletion channel, and this result was also extended to certain channels combining deletions and geometric insertions of uniformly random bits. In this work, we use a simple extension of the original complex-analytic approach to show that these results are examples of a much more general phenomenon: $\exp(O(n^{1/3}))$ traces suffice for mean-based worst-case trace reconstruction over any memoryless channel that maps each input bit to an arbitrarily distributed sequence of replications and insertions of random bits, provided the length of this sequence follows a sub-exponential distribution.