New Bounds for Circular Trace Reconstruction

Arnav Burudgunte Paul Valiant Hongao Wang Purdue University · 2025

Read New Bounds for Circular Trace Reconstruction by Arnav Burudgunte Paul Valiant Hongao Wang Purdue University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02412.txt.

Description

Arnav Burudgunte, Paul Valiant, and Hongao Wang, based at Purdue, work on a puzzle about rebuilding lost data. A hidden string of zeros and ones passes through a channel that deletes each bit at random. Each pass gives only a partial copy, called a trace, and the task is to rebuild the string.

For the circular form of the puzzle, the best known upper and lower bounds sit far apart. That gap is huge, described as exponential in size. The authors narrow it with new bounds, which helps show how many traces recovery truly needs. Sharper bounds tell us how much loss a string can take and still be rebuilt whole.

Catalog record

CREATORArnav Burudgunte Paul Valiant Hongao Wang Purdue University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02412

Browse the full library · About the Tower of Babel