we-solve (beta)

CS-168 · computer science · mathematics · Information and coding theory

Uniform quasipolynomial worst-case trace reconstruction

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

For binary strings of known length $n\ge2$ and known rational retention probability $p\in(0,1]$, seek one randomized multitape Turing machine that reconstructs every input with probability at least $2/3$. At each fixed $p$, its independent ordinary deletion-trace budget should be \[ M(n,p)=\exp\left(O_p((\log n)^3(1+\log\log(2n))^6)\right). \] Its bit time must be polynomial in $n$, the binary encoding length of $p$, and the prescribed trace budget, on every internal random-bit sequence and every trace stream consisting of words of length at most $n$. Preprocessing, finite-precision computation, received bits and output are charged. Only external generation of independent traces is an oracle operation.

Short English statement

Can one uniform binary trace-reconstruction algorithm achieve the specified quasipolynomial trace and bit budgets at every fixed rational retention probability?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-168-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-168

The main theorem supplies one randomized multitape machine for all binary words of length $n\ge2$ and all rational $p\in(0,1]$. It has the stated sample bound, success probability and bit-time bound on every random path and every length-bounded trace stream. At each fixed $p$, this yields precisely the quasipolynomial guarantee asked here.

Uniform quasipolynomial worst-case trace reconstruction

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 122; 2026-10-05), the asserted result is that every binary word can be reconstructed with known rational retention probability using a uniform algorithm with quasipolynomial sample and bit bounds at fixed retention, and polynomial bounds for sufficiently small deletion.

Mathematical statement of the claimed result

Manuscript 1.
For a binary word $x\in\{0,1\}^n$, $n\ge2$, an ordinary deletion trace independently retains each symbol with rational probability $p=a/b\in(0,1]$ and preserves order. Put $q=1-p$, let $L$ be the bit length of the reduced numerator and denominator, and define \[ X(n,p)=\begin{cases}1+\dfrac{\log n}{1+\log(1/q)},&q>0,\\1,&q=0,\end{cases} \qquad B(n,p)=p^{-1}(\log n)X(n,p)^2(1+\log X(n,p))^6. \] The claim gives absolute $C,c\ge1$ and one randomized multitape Turing machine, given $n,p$ in binary, that requests at most \[ M_C(n,p)=\lceil\exp(CB(n,p))\rceil \] independent traces. For each input word $x$, reconstruction succeeds with probability at least $2/3$. Regardless of the internal random tape and of the received stream, provided all its strings have length bounded by $n$, the running time is at most \[ (n+L+M_C(n,p))^c \] bit operations, including preprocessing, finite-precision calculations, received bits and output. Only external generation of independent traces is treated as an oracle operation.

Outline of the argument

For manuscript 1 (family 122; 2026-10-05), low-order trace moments propagate a distinguishing signal through scales using damped products and prescribed frequencies. Positive moment constraints recover prefixes, and a bounded feasibility iteration turns the statistical separation into an explicit finite-precision decoder.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 122; 2026-10-05).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →