Mean-Based Trace Reconstruction over Oblivious Synchronization Channels

Mahdi Cheraghchi, Joseph Downs, João Ribeiro +1

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}))$ trace…