Quantitative lower bounds for trace reconstruction
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/quantitative-lower-bounds-for-trace-reconstruction
curl -X POST /api/v1/records/openai-math/quantitative-lower-bounds-for-trace-reconstruction/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/quantitative-lower-bounds-for-trace-reconstruction/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'