2 papers
cs.DS2026
Quasipolynomial Trace Reconstruction
Arnav Burudgunte, Paul Valiant, Hongao Wang
We show that trace reconstruction on n-bit strings is possible using a quasipolynomial number of traces, for any retention probability p that is at least inverse polylogarithmic in…
cs.DS2025
New Bounds for Circular Trace Reconstruction
Arnav Burudgunte, Paul Valiant, Hongao Wang
The ''trace reconstruction'' problem asks, given an unknown binary string and a channel that repeatedly returns ''traces'' of with each bit randomly deleted with some proba…