2026-07-19T04:53:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25317 2026-03-19T13:03:25Z ddc:004 open_access

New Bounds for Circular Trace Reconstruction Burudgunte, Arnav Valiant, Paul Wang, Hongao Trace reconstruction algorithmic statistics Fourier analysis The "trace reconstruction" problem asks, given an unknown binary string x and a channel that repeatedly returns "traces" of x with each bit randomly deleted with some probability p, how many traces are needed to recover x? There is an exponential gap between the best known upper and lower bounds for this problem. Many variants of the model have been introduced in hopes of motivating or revealing new approaches to narrow this gap. We study the variant of circular trace reconstruction introduced by Narayanan and Ren (ITCS 2021), in which traces undergo a random cyclic shift in addition to random deletions. We show an improved lower bound of Ω̃(n⁵) for circular trace reconstruction. This contrasts with the (previously) best known lower bounds of Ω̃(n³) in the circular case and Ω̃(n^{3/2}) in the linear case. Our bound shows the indistinguishability of traces from two sparse strings x,y that each have a constant number of nonzeros. Can this technique be extended significantly? How hard is it to reconstruct a sparse string x under a cyclic deletion channel? We resolve these questions by showing, using Fourier techniques, that Õ(n⁶) traces suffice for reconstructing any constant-sparse string in a circular deletion channel, in contrast to the best known upper bound of exp(Õ(n^{1/3})) for general strings in the circular deletion channel. This shows that new algorithms or new lower bounds must focus on non-constant-sparse strings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnav Burudgunte and Paul Valiant and Hongao Wang 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.30 urn:nbn:de:0030-drops-253176 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode