Prove TraceReconstruction (openai/math family 122: Superpolynomial lower bounds and quasipolynomial…
Prove TraceReconstruction (openai/math family 122: Superpolynomial lower bounds and quasipolynomial…: a task in openai/math as Harbor environments (Harbor dataset). Context: this statement belongs to family 122 of the release, Superpolynomial lower bounds and quasipolynomial reconstruction from…
The task
Context: this statement belongs to family 122 of the release, *Superpolynomial lower bounds and quasipolynomial reconstruction from deletion traces* (Theoretical computer science). The family as a whole: At every fixed deletion probability in $(0,1)$, reconstructing an arbitrary length-$n$ binary string requires…
Part of raising-heart/openai-math.