{"id":"3b00a9d8-404e-462a-b6fc-98ae2d6cdae7","arxiv_id":"2411.18765","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A near-optimal trace reconstruction algorithm uses O(n log n) traces and polynomial time for strings whose 1s are separated by polylog n zeros, under small constant deletion probability.","lead":"This paper gives a polynomial-time algorithm that reconstructs any binary string from O(n log n) noisy traces, provided consecutive 1s in the string are separated by at least polylog n zeros and deletions are rare. It is the first near-optimal trace guarantee for a broad structured class in the constant-deletion regime.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The paper's main theorem depends on Lemma 3.2, exactly the assumption the reader flagged as most load-bearing. I therefore walked through that lemma's proof rather than the surrounding algorithmic narrative. Lemma 3.4 gives a deterministic contradiction under a k-periodic closeness condition, and the conditioning event fails with probability at most (2δ)^K. Lemma 3.5 splits at the first index where b_h and a_h differ substantially; the two special boundary cases are handled by Lemma 3.4 or by the definition of h. Lemma 3.6 splits at the last index where a_h differs from b_{h-k}; the suffix inherits the condition needed for Lemma 3.5, and the other special case contradicts the badness of h. Lemma 3.8's induction uses the Catalan convolution correctly: for fixed k3=k1+k2, the sum of D_{k1}D_{k2} is at most 100^{-3}D_{k3+1}, and the ratio D_{k+1}/D_k ≤ 4·100^2 makes the resulting series summable under δ≤1/(3·10^6). The constants in the final union bound work because K=C2 log n can be chosen large enough to absorb the n^4 factor. In Section 4, the observed gap counts \tilde a_i are Binomial around (1-δ)a_i and the estimates b_i approximate the same quantities, so Lemma 3.1 and Lemma 3.2 apply; a small amount of constant slack absorbs cases where \tilde a_i is slightly below L. The fine estimation step conditions on a rare bad event of probability O(n^{-10}), which only shifts the mean by O(n^{-9}) and does not affect rounding. I found no mathematical step that would invalidate Theorem 1.1. The proof has several fixable typos but no load-bearing gap, so the reader's ACCEPT verdict stands unchanged.","tokens_in":21529,"tokens_out":47224,"duration_ms":390354,"concrete_test":"As a verification step, implement the probabilistic process of Section 3 for moderate n (e.g., n=10^4, L=C log^8 n, δ=1/(3·10^6)) with adversarially chosen a,b in [L,n], and estimate P(f_m<m) over at least 10^6 trials; check that the empirical probability is below 200δ. Separately, re-derive the coefficient of the recursive sum in Lemma 3.6 to confirm the extra factor of 2 is correct and that the two special split cases contribute only (2δ)^K.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed the central technical engine, Lemma 3.2, and its recursive proof in Lemmas 3.4–3.8. The case analysis closes: Lemma 3.5 applies Lemma 3.4 when the b-sequence is everywhere close to a, and otherwise splits at the first bad index; Lemma 3.6 handles the general case by splitting at the last bad index and reducing the suffix to Lemma 3.5. The special split cases (0,0,0,k) and (0,0,k,0) are either bounded by (2δ)^K or shown impossible using the defining badness of the split index. The Catalan recursion in Lemma 3.8 has the right convolution constants: summing C_{k1}C_{k2} gives C_{k3+1}, so the 100^{-3}D_{k3+1} bound and the subsequent D_{k+1}/D_k ≤ 4·100^2 bound make the induction work. The application in Section 4 correctly conditions on observed gap lengths being close to the estimates, so Lemma 3.1 prevents being ahead and Lemma 3.2 bounds being behind. The fine-estimation phase's forward/backward certification succeeds except with probability O(n^{-10}), and the target gap is independent of the certification event up to that negligible error. The only issues I found are expository: swapped case labels in Lemmas 3.5/3.6, a 'wi+r=0' that should read 'wi+r=1', and a pseudocode assumption about trace length. None of these affects the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies trace reconstruction for L-separated strings, i.e., strings in which the run of zeros between any two consecutive ones has length at least L. The main result, Theorem 1.1, is an algorithm that, for L >= C log^8 n and deletion probability at most a sufficiently small universal constant, reconstructs the string with high probability using O(n log n) independent traces and polynomial time. The algorithm works by maintaining estimates of the gap lengths between consecutive ones and repeatedly aligning retained ones in a trace to ones in the original string. The central technical contribution is an analysis of a probabilistic alignment process in which only ones are deleted: Lemma 3.1 shows the process is never ahead except with probability n^{-10}, and Lemma 3.2 bounds the probability of being behind by 200 delta. The full reconstruction combines a coarse estimation phase using medians, a fine estimation phase using forward and backward alignment with a certification step, and a proof that the certified gap measurements are essentially unbiased.","tokens_in":21784,"tokens_out":35904,"duration_ms":310156,"significance":"If the result is correct, it is a substantial advance: it gives the first polynomial-time, O(n log n)-trace algorithm for a broad class of strings under constant deletion probability, and the O(n log n) sample bound is within a logarithmic factor of the Omega(n) information-theoretic lower bound for distinguishing two adjacent single-one strings. The proofs are self-contained and the constants are fixed up front rather than fitted to the target bound; there is no parameter fitting or circularity. The amortization argument behind Lemma 3.8 is intricate but appears to close, and the reduction from the real deletion channel to the simplified process in Section 4 is carefully argued. The paper also correctly identifies and credits the relation to earlier work on parameterized and approximate trace reconstruction. The main caveats are expository: several typos and notation slips in the central proof sections make the paper harder to verify than it should be.","major_comments":[],"minor_comments":[{"comment":"In the final case split, the text defines i+r as the first index after i with wi+r = 0, but then conditions on wi+r = wi' = 1 and on f_{i+r}. This is internally inconsistent: f_{i+r} is only defined when wi+r = 1. The intended statement should presumably be that i+r is the first retained index after the initial run of deletions, so that wi+r = 1. As written, this step in the proof of the main alignment lemma cannot be followed, although the surrounding p_{K/2} bound indicates the intended fix.","section":"§3.2 (proof of Lemma 3.2)"},{"comment":"In the treatment of the special cases, the labels 'former' and 'latter' are swapped relative to the enumeration (0,0,0,k) and (0,0,k,0), and the displayed sums contain repeated variables 'k2,k2' that should be 'k1,k2'. These are presentation errors, but they occur in a delicate induction and should be corrected.","section":"§3.2 (Lemmas 3.5 and 3.6)"},{"comment":"The Cauchy-Schwarz step in the proof of Lemma 3.1 appears to omit a square root: the display should have sqrt(|j'-j|) rather than |j'-j| before the bound 4 C1 log n sqrt(b_{j:j'}). With the printed text, the displayed inequality is not valid as written.","section":"§3.1 (Lemma 3.1)"},{"comment":"The phrase 'conditioned on this event holding' should make explicit that the event includes the retention of both the mth and (m+1)th ones; otherwise the claimed conditional distribution of r_{q+1} - r_q - 1 as Bin(a_m, 1-delta) is not guaranteed, since the next retained one may be later if the (m+1)th one is deleted.","section":"§4.1 (Lemma 4.1)"},{"comment":"The pseudocode assumes the trace contains at least t-1 ones when indexing r_q for 1 <= q <= t-1; it should index by the actual number of ones in the given trace. In addition, the text says 'there are t-1 ones' immediately after a depiction with t ones, and Algorithm 2 says 't equals the number of 0s in x' where it should say the number of ones.","section":"§4 (Algorithms 1–3 and surrounding text)"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one before you sign off on a survey of parameterized trace reconstruction. Aamand, Liu, and Narayanan give the first polynomial-time algorithm that exactly reconstructs an L-separated string (gaps between ones at least C log^8 n) from O(n log n) traces under a small constant deletion probability, matching the Omega(n) information-theoretic lower bound up to a log factor. That is a real step beyond KMMP21, which needed sparsity plus separation, and DRSR21, which only gave approximate reconstruction.\n\nThe main technical content is the sequential alignment procedure and its amortized analysis. Lemma 3.1 (never ahead) is straightforward concentration, but Lemma 3.2 (rarely behind) is the heart. I checked the recursive splitting in Lemmas 3.4-3.8, including the Catalan convolution in Lemma 3.8; the constants work, and the special split cases (0,0,0,k) and (0,0,k,0) are handled correctly. The stress-test note agrees, and I didn't find a gap either. The reduction from the actual deletion channel to the simplified process in Section 4 is careful: conditioning on the observed gaps being large is legitimate because L is polylog n and delta is tiny, and the fine estimation's forward/backward certification correctly kills the rare misalignment events.\n\nSoft spots, in proportion. The deletion probability is capped at 1/(3*10^6) and separation must be C log^8 n; the authors openly say they did not optimize constants and don't expect straightforward changes to get delta around 1/2 or L = O(log n). So the practical regime is limited, but that is a boundary of the technique, not an error. The proofs are not machine-checked, and an induction this intricate is exactly where a subtle off-by-one could hide; I found none, but formal verification would raise confidence. There are minor typos: Algorithm 2 says 't equals the number of 0s' (should be 1s), Section 4 says 't-1 ones' (should be t), the case labels in Lemmas 3.5/3.6 are swapped in places, and Algorithm 1's pseudocode assumes the trace contains enough 1s. None of these affect the theorems.\n\nResearchers working on trace reconstruction and deletion channels will want this. Bottom line: it deserves a serious referee. It is a genuine advance for a natural class of hard instances, the proof structure is coherent, and the limitations are stated honestly. I'd send it to peer review; the referee should focus on Lemmas 3.4-3.8 and the independence argument in Lemma 4.4. Reading group? Maybe — the result is exciting enough, but the proof is heavy for a casual session. I'd cite it if I wrote anything nearby in the next year.","headline":"Genuinely new near-optimal trace reconstruction for separated strings; the proof is intricate but the argument holds up on close reading.","tokens_in":22367,"tokens_out":7677,"would_cite":true,"duration_ms":106169,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any binary string with zero-runs of length at least $C(\\log n)^8$ between consecutive 1s can be reconstructed from $O(n\\log n)$ traces in polynomial time, for small constant deletion probability.","keywords":["trace reconstruction","deletion channel","L-separated strings","alignment algorithm","sample complexity","polynomial-time algorithm","Catalan numbers","constant deletion probability"],"falsifier":"A concrete check is to compute, by dynamic programming over the random variables $w_i$, the exact probability that the alignment procedure is behind when processing the $m$-th surviving $1$, for two identical strings whose zero-run lengths are all equal to $L=C(\\log n)^8$ and with $\\delta=1/(3\\cdot10^6)$. If that probability exceeds the claimed $200\\delta$, Lemma 3.2 is false and the main theorem collapses. Simulating the recursion for $p_k$ and checking $p_k\\le 100^{2k-1}C_k\\delta^k$ for all $k\\le C_2\\log n$ would test the paper's core inequality directly.","tokens_in":21301,"feed_emoji":"🧬","tokens_out":16577,"duration_ms":135568,"temperature":0.7,"pith_summary":"This paper proves that trace reconstruction can be solved with $O(n\\log n)$ traces and polynomial time for every $L$-separated binary string with $L \\ge C(\\log n)^8$, provided the deletion probability $\\delta$ is a sufficiently small constant. An $L$-separated string is one in which every two consecutive $1$s are separated by at least $L$ zeros, so the class includes strings with many ones, not just sparse strings. The best known algorithms for arbitrary strings require $\\exp(\\tilde{O}(n^{1/5}))$ traces, and a simple argument shows $\\Omega(n)$ traces are necessary, so the paper's bound is optimal up to a logarithmic factor. The proof reduces reconstruction to a left-to-right alignment procedure and then shows, through a Catalan-number recursion, that the procedure is almost never behind the true alignment.","feed_headline":"Mildly separated strings reconstructed with near-optimal traces","feed_subtitle":"A new alignment algorithm recovers any such string exactly, in polynomial time, even with constant deletion.","key_machinery":"The central object is the alignment procedure (Algorithm 1). Given estimates $b_0,\\ldots,b_{m-1}$ of the first $m$ zero-run lengths, it scans a trace from left to right and, for each surviving $1$ in the trace, chooses the smallest position $j'$ in the original string such that the observed number of zeros since the previous aligned $1$ matches the estimated cumulative gap $b_{j:j'}$ up to tolerance $C_0\\log n\\sqrt{b_{j:j'}}$. Choosing the smallest plausible position enforces the 'never ahead' property with probability $1-n^{-10}$ (Lemma 3.1). The harder direction is Lemma 3.2, which bounds how often this greedy choice is behind the true position. Its proof splits the pair of sequences $a$ (true gaps) and $b$ (estimates) into locally similar and locally different stretches: where $a$ and $b$ are similar, a periodic-structure argument shows falling a full period behind has probability at most $(2\\delta)^K$; where they differ, the alignment must cross a boundary, and the probability factors into independent subproblems. Those subproblems satisfy a recursion whose coefficients are Catalan numbers, giving $p_k\\le 100^{2k-1}C_k\\delta^k$ for falling $k$ steps behind.","core_discovery":"The central claim is Theorem 1.1: for a string $x\\in\\{0,1\\}^n$ whose zero-run lengths between consecutive $1$s are all at least $L\\ge C(\\log n)^8$, and for any deletion probability $\\delta\\le c_0$ (a small universal constant), an algorithm recovers $x$ exactly with high probability from $N=O(n\\log n)$ traces in $\\mathrm{poly}(n)$ time. The load-bearing lemma is Lemma 3.2: in the idealized process where only $1$s can be deleted, if every candidate gap length lies in $[L,n]$, then the alignment output $f_m$ satisfies $f_m\\ge m$ with probability at least $1-200\\delta$. The proof of that lemma gives an amortized recursive bound: whenever a run of deleted $1$s could make the algorithm fall $k$ steps behind, the same structure lets an already-behind algorithm catch up, and the resulting recursion is controlled by Catalan numbers. The full pipeline first learns the number of ones, then obtains crude estimates of every zero-run length by taking medians of aligned trace gaps, and then refines them to exact values by averaging over traces that pass a two-sided forward/backward alignment check.","pith_inferences":["Beyond the paper: the never-ahead/never-behind decomposition is a reusable template. Any alignment clue that is provably never wrong in one direction can be combined with a two-sided check to convert a constant-probability success into a $1-n^{-10}$ event; $L$-separated zero runs are one way to instantiate that template, but the same two-sided verification might transfer to other repetitive string","The exponent $8$ in $(\\log n)^8$ is not optimized, and the paper explicitly says its methods will not reach $L=O(\\log n)$. An open question it leaves is where the true threshold lies: whether separation $C\\log^2 n$ or $C\\log n$ already admits a polynomial-time exact algorithm with a different amortization, or whether a new obstruction appears below polylogarithmic separation.","Because the fine phase already discards traces that fail the forward/backward check, a natural weakened variant is approximate reconstruction with fewer traces: instead of averaging enough traces to round to the exact gap, one could stop at a specified edit distance. Prior work achieves $O((\\log n)/\\varepsilon^2)$ traces for very long runs in the approximate setting; whether the two-sided alignmen"],"forward_implications":["For every input string with $L\\ge C(\\log n)^8$ and small constant $\\delta$, the algorithm outputs the exact string with high probability using $O(n\\log n)$ traces and polynomial time.","The $O(n\\log n)$ sample complexity is within a logarithmic factor of optimal, because distinguishing two strings with a single $1$ in adjacent positions requires $\\Omega(n)$ traces.","The class of strings handled is not sparse: it can contain up to $n/\\mathrm{polylog}\\, n$ ones, whereas the previous parameterized polynomial-time algorithm needed the number of ones to be polylogarithmic at this separation level.","The pipeline separates coarse median-based estimation from fine averaging-based estimation, with a two-sided alignment check that discards misaligned traces; this is how an alignment event that succeeds only with probability $1-O(\\delta)$ is upgraded to an almost-sure event."],"supporting_citations":[{"why":"Supplies the best known general upper bound, the benchmark that the paper's polynomial-time result qualitatively improves.","marker":"[Cha21b]"},{"why":"Supplies the best known general lower bounds for trace reconstruction, which frame the sample-complexity comparison.","marker":"[Cha21a]"},{"why":"Gives the earlier parameterized polynomial-time algorithm for strings with few ones; the paper's L-separated result broadens that class to many ones.","marker":"[KMMP21]"},{"why":"Motivates the hard regime of repetitive strings and gives polynomial-time low-deletion-rate reconstruction; the paper treats long zero runs as the simplest repetitive-block test bed.","marker":"[CDL+21b]"},{"why":"Provides approximate trace reconstruction results for strings with long zero runs, the approximate counterpart that the exact reconstruction result goes beyond.","marker":"[DRSR21]"}],"fun_headline_variants":["Trace reconstruction: near-optimal for mildly separated strings","Mildly separated strings recovered with O(n log n) traces","Near-optimal trace reconstruction for separated binary strings","Constant-deletion recovery of mildly separated strings","Strings with sparse ones: nearly-linear trace complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire result rests on the inequality $p_k\\le 100^{2k-1}C_k\\delta^k$ for the probability that the alignment falls $k$ steps behind, and that inequality is proven only under the assumptions $L\\ge C(\\log n)^8$ and $\\delta\\le 1/(3\\cdot10^6)$; if it fails for some pair of well-separated sequences, the claimed $O(n\\log n)$ guarantee is not established.","fun_headline_variants_meta":{"raw":{"variants":["Trace reconstruction: near-optimal for mildly separated strings","Mildly separated strings recovered with O(n log n) traces","Near-optimal trace reconstruction for separated binary strings","Constant-deletion recovery of mildly separated strings","Strings with sparse ones: nearly-linear trace complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000596,"raw_usage":{"total_tokens":2807,"prompt_tokens":979,"completion_tokens":1828,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":1753}},"tokens_in":595,"tokens_out":1828,"duration_ms":13059,"temperature":1.0,"reasoning_tokens":1753,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:54:58.108695+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check is to compute, by dynamic programming over the random variables $w_i$, the exact probability that the alignment procedure is behind when processing the $m$-th surviving $1$, for two identical strings whose zero-run lengths are all equal to $L=C(\\log n)^8$ and with $\\delta=1/(3\\cdot10^6)$. If that probability exceeds the claimed $200\\delta$, Lemma 3.2 is false and the main theorem collapses. Simulating the recursion for $p_k$ and checking $p_k\\le 100^{2k-1}C_k\\delta^k$ for all $k\\le C_2\\log n$ would test the paper's core inequality directly.","supporting_citations":[],"review_version":1}