{"ID":5938074,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-08T01:33:34.630854101Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04073","arxiv_id":"2607.04073","title":"Quasipolynomial Trace Reconstruction","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.","short_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.","url_abs":"https://arxiv.org/abs/2607.04073","url_pdf":"https://arxiv.org/pdf/2607.04073v1","authors":"[\"Arnav Burudgunte\",\"Paul Valiant\",\"Hongao Wang\"]","published":"2026-07-05T01:33:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.IT\"]","methods":"[]","has_code":false}