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
| CREATOR | Arnav Burudgunte Paul Valiant Hongao Wang Purdue University |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-02412