{"id":"openai-math/quantitative-lower-bounds-for-trace-reconstruction","pdf":"https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026","tags":["trace-reconstruction","probability","sample-complexity"],"score":0,"title":"Quantitative lower bounds for trace reconstruction","domain":"Theoretical computer science","family":"122","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"Exact worst-case reconstruction of a binary word from independent deletion traces requires $`n^{\\Omega(\\log\\log n)}`$ samples for every fixed deletion probability $`q\\in(0,1)`$, even with unrestricted computation and any fixed positive success probability. This gives a negative answer to the polynomial-sample question for binary trace reconstruction. More generally, when $`q^3\\log n\\to\\infty`$, we prove a lower bound of $`n^{c\\log(q^3\\log n)}`$ samples for every fixed $`0\\lt c\\lt 1/(4\\log2)`$. Here q is the known deletion probability, and all logarithms are natural.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Quantitative trace-reconstruction bounds with a uniform decoder"}