{"id":"openai-math/Uniform-quasipolynomial-time-trace-reconstruction","pdf":"https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf","url":"https://github.com/openai/math/tree/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026","tags":["trace-reconstruction","learning-theory","theoretical-computer-science","deletion-channels"],"score":0,"title":"Uniform quasipolynomial-time trace reconstruction","domain":"Theoretical computer science","family":"122","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give a uniform algorithm that reconstructs every binary string from independent deletion traces when its length and rational retention probability are known. For each fixed retention probability, both the number of traces and the bit complexity are quasipolynomial in the string length. More generally, we give an explicit sample bound uniform over all rational retention probabilities, with running time polynomial in the sample budget and the binary input length. If the deletion probability is at most $`n^{-\\varepsilon}`$ for fixed ε > 0, the sample and running-time bounds are polynomial.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{},"formalized":false,"family_title":"Quantitative trace-reconstruction bounds with a uniform decoder"}