The reviewed record of science sign in
Pith

arxiv: 2607.04073 · v1 · pith:L6VNZFUC · submitted 2026-07-05 · cs.DS · cs.IT· math.IT

Quasipolynomial Trace Reconstruction

Arnav Burudgunte , Paul Valiant , Hongao Wang This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:L6VNZFUCrecord.jsonopen to challenge →

classification cs.DS cs.ITmath.IT
keywords quasipolynomialreconstructiontraceinverseleastn-bitnumberpolylogarithmic
0
0 comments X
read the original abstract

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 n.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.