New Lower Bounds for Trace Reconstruction

2019/05/08 by Zachary Chase, Chase, Zachary · 2 citations
Computer Science · Medicine · #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Medical Image Segmentation Techniques #Medical Imaging Techniques and Applications #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1905.03031

openalex publication_date 2019/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We improve the lower bound on worst case trace reconstruction from Ω(\fracn^5/4√(log n)) to Ω(\fracn^3/2log⁷ n). As a consequence, we improve the lower bound on average case trace reconstruction from Ω(\fraclog^9/4n√(loglog n)) to Ω(\fraclog^5/2n(loglog n)⁷).

Cited by

• New Bounds for Circular Trace Reconstruction
• Trace Reconstruction with Language Models

Related

• Lower bounds for trace reconstruction
• New upper bounds for trace reconstruction
• Near-Optimal Trace Reconstruction for Mildly Separated Strings
• Trace Reconstruction: Generalized and Parameterized
• Trace reconstruction with exp( O( n^1/3 ) ) samples