Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 122: lower bounds and uniform algorithms for deletion-trace reconstruction

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This account reports pinned publisher claims; it is not an independently checked proof.

The question in plain language

A deletion channel takes a binary string and independently removes characters, preserving the order of those that remain. Each resulting shortened string is a trace. Trace reconstruction asks how many independent traces are needed to recover an unknown original string, and whether reconstruction can be carried out efficiently.

Family 122 claims both an unexpectedly strong worst-case sample lower bound and uniform quasipolynomial upper bounds for a specified parameter regime.

A small example

If the input is 10110, a deletion channel could return 110, 10, or the empty string. One trace generally does not identify the original string. Many independent traces offer complementary information, but positional ambiguity remains: a 1 surviving in one trace cannot be directly matched to its original index.

The distinction between sample complexity and computation matters. An algorithm may use relatively few traces but require substantial time to process them. The publisher claims bounds on both for its decoder, not just an information-theoretic existence result.

What is known

The protected Family 122 catalogue identifies three manuscripts: one on a uniform quasipolynomial decoder, one on latest-anchor induction with spectrally compact masks, and one on quantitative lower bounds.

The pinned publisher overview claims that for every fixed deletion probability \(q\in(0,1)\), worst-case reconstruction of length \(n\) binary strings requires

\[ n^{\Omega(\log\log n)} \]

independent traces. This is a superpolynomial sample lower bound, and is specifically a worst-case claim; it must not be generalized to every input string.

Separately, a uniform decoder is claimed to use quasipolynomially many samples and quasipolynomial running time for known fixed rational retention probabilities, where retention probability is \(1-q\). For the parameter regime where deletion probability satisfies \(q\le n^{-\varepsilon}\) for fixed \(\varepsilon>0\), the overview claims polynomial sample and runtime bounds in the input and parameter encoding.

These statements refer to different probability regimes. The sparse-deletion polynomial claim must not be substituted for the fixed-positive-deletion lower bound, and the rational/known retention qualifier must be preserved.

GCL verification state

Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The protected catalogue identifies three PDFs and the pinned overview describes their qualitative and quantitative claims.

This documentary pass does not verify the indistinguishable-string construction, minimax error criterion, anchor induction, spectral mask estimates, decoding success probability, or uniform bit-complexity accounting. No Family 122-specific accepted critical proof audit, Comparator result, formal elaboration, or MATHCERT certificate is asserted.

What remains

Read all three manuscripts and extract their exact reconstruction success probabilities and whether the worst-case lower bound concerns arbitrary algorithms or a restricted class. Verify the meaning of \(n^{\Omega(\log\log n)}\) with all constants and fixed-parameter dependencies.

Audit the uniform decoder's assumptions on known rational retention rates, representation of probabilities, sample counts, runtime and any dependence on error probability. Distinguish independent deletion traces from correlated or position-labelled observations. Check the transition between fixed deletion probability and \(q\le n^{-\varepsilon}\) without assuming a single bound covers both.

Run source-critical review and mathematical Markdown/MkDocs regression, then protected merge/readback. Editorial admission does not certify trace-reconstruction claims.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. The reconstruction lower bounds and decoder guarantees remain publisher-reported claims requiring independent mathematical verification.


Indexed primary manuscript paths: