A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction
We give an improved worst-case sample bound for reconstructing a string from independent deletion traces, with its length and retention probability known. For each fixed retention probability, the number of traces is quasipolynomial: the logarithm of the sample budget is $O((\log n)^3(1+\log\log(2n))^6)$. If the deletion probability is at most $n^{-\varepsilon}$ for fixed ε > 0, polynomially many traces suffice. These bounds apply to binary strings and to strings of general symbols observed exactly. They concern sample complexity and do not assert an efficient reconstruction algorithm or…
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction
curl -X POST /api/v1/records/openai-math/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-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/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'