{"id":"0c907dc4-e6dc-4fb0-b214-199c7462bf26","arxiv_id":"2412.00674","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Worst-case probability strings require e^{Ω(√n)} traces to distinguish under deletions, while random probability strings are recoverable to ℓ1 error ε with poly(n,1/ε) traces.","lead":"Researchers studied a new version of the classic string-recovery problem where each position holds a probability instead of a fixed bit, and traces are random samples with deletions. They proved that some probability strings are exponentially hard to recover in the worst case, while random strings are easy to recover with only polynomially many samples.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (6) in Lemma 7 is numerically false at n=3, so the moment-generating-function bound underpinning the worst-case lower bound is not established as written.","rationale":"The reader's weakest assumption was the unbiasedness-after-conditioning step in Algorithm 2. I agree that Section 4 asserts rather than proves this, but that gap is readily closable: conditioning on an event of probability 1−γ changes any bounded estimator by O(γ), and the lemmas provide failure probability poly(1/m), so a quantitative bound can be supplied. The lower-bound proof is different: it is the paper's strongest contribution, and a false identity at the heart of Lemma 7 is a concrete mathematical error, not merely a missing argument. It is likely repairable, so I do not recommend rejection; the manuscript should be accepted only after Lemma 7's moment-generating-function computation is corrected and verified. The verdict therefore stays CONDITIONAL, matching the reader's conclusion.","tokens_in":19785,"tokens_out":38910,"duration_ms":363223,"concrete_test":"Compute Eq. (6) at t=0 for n=3: direct integration gives ∫_{−π}^{π} cos^3(ξ'/2) dξ' = 8/3, whereas the displayed formula gives 2^4/C(3,1)=16/3; also check the claimed inequality 2^{n+1}/C(n,(n−1)/2) ≤ √(8π/n) for n=3, which gives 16/3 > 2.89. Then re-derive g(t) from the binomial expansion of cos^n(ξ'/2) and recompute the α threshold in Lemma 7 to verify whether |f(ξ)|≤2e^{−√n} still holds after correcting Eq. (6).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3's lower bound (Theorem 5) rests on Lemma 7, whose proof bounds g(t)=∫_{−π}^{π} cos(ξ'/2)^n e^{tξ'} dξ'. Equation (6) asserts g(t)=2^{n+1} cosh(πt)/(C(n,(n−1)/2) ∏_{j=0}^{(n−1)/2}(1+t²/(j+1/2)²)), and the proof then relies on 2^{n+1}/C(n,(n−1)/2) ≤ √(8π/n). This is internally inconsistent: for n=3, the left side of Eq. (6) at t=0 is 8/3, while the right side is 16/3; asymptotically the coefficient is ~√(2π n), not ~√(8π/n). Since Lemmas 8 and Theorem 5 use the resulting bound on g to conclude |f(ξ)|≤2e^{−√n}, the written proof of the lower bound does not go through. The error may be a normalization slip and the bound may be repairable, but as written the central Fourier estimate is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a generalized trace reconstruction problem in which the unknown object is a length-n string of probabilities S = p_1,...,p_n, and each trace is generated by first sampling a binary string with independent bits having those probabilities and then deleting each bit independently with probability δ. The main results are: (i) a worst-case lower bound (Theorems 2 and 5) claiming that for deletion probability δ ≥ c/√n there exist two probability vectors with constant ℓ∞ distance and ℓ1 distance Θ(√n) whose trace distributions have total variation distance e^{-Ω(√n)}, implying that e^{Ω(√n)} traces are needed to distinguish them; and (ii) an average-case upper bound (Theorem 3) claiming that for iid uniform entries and δ ≤ 10^{-7}, poly(n,1/ε) traces and computation suffice to recover S to ℓ1 error ε with high probability. The lower-bound proof centers on a Fourier/moment-generating-function analysis of an alternating sum, with Lemma 7 as the key technical step; the upper-bound proof gives two algorithms that identify and align deletion-free chunks without looking at the contents of the chunk being estimated.","tokens_in":19962,"tokens_out":25401,"duration_ms":248690,"significance":"The results are natural and potentially significant if the proofs can be repaired. The worst-case lower bound would be a strong super-polynomial sample-complexity lower bound for this generalized deletion-channel model, and the Fourier/moment-generating-function technique is an interesting new tool for trace-reconstruction-style indistinguishability arguments. The average-case algorithm is also notable for its deliberate separation of localization from estimation, which avoids the compounding bias of incremental methods. The paper is self-contained, the constructions are explicit, and the upper-bound algorithm is concrete. However, as written, the central Fourier estimate behind the lower bound is incorrect, and the unbiasedness step of the upper-bound proof is asserted rather than proved; the stated theorems are therefore not established by the manuscript in its current form.","major_comments":[{"comment":"Equation (6) is not correct. At t=0 and n=3, the left-hand side is ∫_{-π}^{π} cos^3(ξ'/2)dξ' = 8/3, while the right-hand side is 16/3. Asymptotically, the coefficient 2^{n+1}/C(n,(n-1)/2) on the right-hand side is ~√(2π n), so the bound 2^{n+1}/C(n,(n-1)/2) ≤ √(8π/n) asserted in Eq. (7) cannot hold. Since Eqs. (7)-(9) are the basis for the tail bound and hence for the conclusion |f(ξ)| ≤ 2 e^{-√n}, Lemma 7 is not established as written. Lemmas 8 and Theorem 5 inherit this gap, and the lower-bound sample-complexity claim is therefore unsupported.","section":"Section 3, Lemma 7, Eq. (6)"},{"comment":"The proof asserts that after conditioning on the successful alignment of Algorithm 2, the coordinates of the returned chunks are “close to independent unbiased estimates,” but it provides no quantitative bound. The grouping step of Algorithm 2 is based on Hamming distances between the M-chunks themselves, so the conditioning event is not independent of the values being averaged; a threshold that preferentially admits chunks close to a seed can bias the averaged estimates. The paper needs an explicit argument (e.g., a coupling that shows the conditional distribution is within inverse-polynomial total variation distance of the unconditional one, or a direct bound on the conditional bias of each estimated coordinate) to complete the ε-error guarantee of Theorem 3.","section":"Section 4, final paragraph of the proof of Theorem 3"}],"minor_comments":[{"comment":"The statements “δ ≥ c√n” should be “δ ≥ c/√n”; otherwise the condition is impossible for large n, contradicting the proof, which uses δ ∈ [320/√n, 1/2].","section":"Theorem 2, Theorem 5, and proof of Theorem 5"},{"comment":"The proof fixes w = 10000 log m, but for ε so small that log m exceeds Θ(n), the chunks are longer than the string length n. The choice of m as a function of n and ε needs to be specified so that w ≤ n/3, or the small-ε regime must be handled separately, since the theorem quantifies over all ε > 0.","section":"Section 4, Algorithm 1 parameterization"},{"comment":"There are minor typographical issues: “for worst-case string s S” in the abstract, and the “eΩ(√n)” formatting in the opening of Section 1; these should be corrected.","section":"Abstract and Section 1"},{"comment":"The factor “(2π−2)” in the bound of Lemma 8 appears suspicious; the convolution-domain measure should be stated precisely so the reader can verify the constant.","section":"Lemma 8, first display"}],"recommendation":"major_revision","confidential_remarks":"The numerical failure of Eq. (6) at n=3 is decisive and not a harmless typo: the stated identity has the wrong asymptotic order. I would ask the authors to supply a correct moment-generating-function estimate for Lemma 7 before further consideration. The upper-bound gap is likely repairable with a standard coupling/total-variation argument, but it must be written out. If the lower-bound lemma cannot be repaired, Theorem 5 should be withdrawn from the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The model is genuinely new: a string of probabilities rather than bits, with deletion applied after sampling. That alone is worth something, and the paper positions it correctly against BCF+19 population recovery. The lower-bound idea—comparing two parity-based strings, reducing to a partial deletion process, then bounding an alternating sum via Fourier transforms and moment generating functions—is clever and potentially reusable. The average-case algorithm's one-shot localization/mapping split is also a nice design, avoiding the iterative bias of earlier trace-reconstruction approaches. The writing is clear, and the citations look fair.\n\nThe problem is that the main lower-bound proof as written does not hold. Lemma 7's equation (6) is numerically wrong: for n=3, the left side g(0) is 8/3, while the asserted closed form gives 16/3. This is not a harmless typo in a constant. The coefficient 2^{n+1}/C(n,(n-1)/2) is asymptotically sqrt(2πn), not sqrt(8π/n). The subsequent bound g(t) ≤ e^{2t^2/n} sqrt(8π/n) is therefore off by a factor of about n. That destroys the key step where αg(t) < 1 is needed at t = ±√n: with the stated α ≤ √n/(4e^2√(2π)), αg(√n) would be Θ(n), not bounded by 1. So the proof of Theorem 5 does not go through as written. It may be repairable—possibly a normalization slip in defining the Fourier transform or the unwrapped h—but it is load-bearing.\n\nThe average-case section has a separate, quieter gap. The final analysis explicitly concedes that independence fails after conditioning on successful alignment in Algorithm 2, then asserts the estimates are “close to independent unbiased” without a quantitative bound. That is exactly the kind of selection-bias worry that needs an argument. The endpoint padding trick is also hand-waved. These feel more patchable than the Lemma 7 error, but they are real.\n\nI would not recommend judging this paper on the current version. The lower bound is the core contribution, and its central technical estimate is false as written. That said, the underlying approach is serious enough that a good referee might help the authors fix it, and the model deserves attention. Send it to review, but make clear to the editor that the proof of the main theorem is currently invalid and needs substantial revision.","headline":"Novel model and a clever Fourier/MGF idea, but Lemma 7 contains a numerical error that voids the worst-case lower bound as written, and the average-case analysis has an unquantified conditioning gap.","tokens_in":20522,"tokens_out":3251,"would_cite":false,"duration_ms":121419,"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":"This paper proves that deleting bits from a length-$n$ string of probabilities can hide worst-case instances so well that any algorithm needs $2^{\\Omega(\\sqrt n)}$ traces, while random instances are recoverable with polynomially many…","keywords":["generalized trace reconstruction","deletion channel","worst-case lower bound","average-case algorithm","Fourier transform","moment generating function","total variation distance","random probability strings"],"falsifier":"Run Algorithm 1 and Algorithm 2 on a random string with, say, $n=10^5$ and $\\delta=10^{-7}$, and compare the averaged returned estimates for each coordinate with the true $p_k$; if the mean bias after successful alignment exceeds the promised $\\epsilon$ on a non-negligible fraction of coordinates, the unquantified independence step in the proof is wrong and the average-case theorem would not hold as stated.","tokens_in":19511,"feed_emoji":"🧬","tokens_out":21299,"duration_ms":187386,"temperature":0.7,"pith_summary":"The paper introduces a generalization of trace reconstruction in which the hidden object is not a binary string but a length-$n$ string $S=p_1,\\ldots,p_n$ of probabilities in $[0,1]$; each trace is produced by sampling a binary string with independent Bernoulli($p_i$) bits and then deleting each bit independently with probability $\\delta$. The paper tries to establish two complementary facts. In the worst case, for deletion probability $\\delta\\ge c/\\sqrt n$, there are two probability strings differing by constant $\\ell_\\infty$ distance and by $\\ell_1$ distance $\\Theta(\\sqrt n)$ whose trace distributions have total variation distance $e^{-\\Omega(\\sqrt n)}$, so no algorithm using fewer than $2^{\\Omega(\\sqrt n)}$ traces can tell them apart. In the average case, when the $p_i$ are drawn independently and uniformly from $[0,1]$, the paper claims a polynomial-time algorithm using $\\mathrm{poly}(n,1/\\epsilon)$ traces recovers $S$ to $\\ell_1$ error $\\epsilon$ for every constant deletion probability $\\delta\\le 10^{-7}$. A sympathetic reader would care because standard trace reconstruction is the special case where all $p_i\\in\\{0,1\\}$, so the result shows that relaxing the bit constraint to probabilities preserves the super-polynomial worst-case difficulty while making random instances provably easy.","feed_headline":"Deletion hides worst-case strings from exponentially many traces","feed_subtitle":"Random probability strings, by contrast, are recoverable with polynomially many traces and time.","key_machinery":"For the lower bound, the central object is the pair $S_e,S_o$ of even/odd binomial probability strings and the identity that rewrites the indistinguishability computation as the alternating sum $\\sum_r(-1)^r y(r)$, i.e., the Fourier transform of $y$ evaluated at $\\xi=\\pm\\pi$. The proof's engine is the moment generating function of the (unwrapped) Fourier transform of the product of binomials: it computes the MGF in closed form from $\\cos(\\xi/2)^n$, bounds it by $e^{2t^2/n}\\sqrt{8\\pi/n}$, and converts the resulting tail bound into a pointwise decay $e^{-\\Omega(\\sqrt n)}$ away from $\\xi=0$; monotonicity of the transform then bounds the value at the alternating frequency. For the average case, the carrying mechanism is Algorithm 1's 'localize outside, estimate inside' rule: a middle chunk $M$ of a trace is returned only when the flanking chunks $L$ and $R$ match chunks of many reference traces at separation at most $w$ and never more than $w$, which guarantees $M$ is deletion-free while keeping the values inside $M$ unbiased because the algorithm never inspects them.","core_discovery":"The central discovery is a pair of probability strings whose outputs through the deletion channel are exponentially close even though the strings themselves are far apart. The strings are supported on even and odd positions respectively, with $S_e(i)=\\alpha\\,\\mathrm{bin}(n,\\tfrac12,i)$ for even $i$ and zero otherwise, and $S_o(i)=\\alpha\\,\\mathrm{bin}(n,\\tfrac12,i)$ for odd $i$, where $\\alpha$ may be as large as $\\Theta(\\sqrt n)$. For $\\delta\\ge c/\\sqrt n$ the total variation distance between a trace from $S_e$ and a trace from $S_o$ is at most $e^{-\\Omega(\\sqrt n)}$, even though $\\|S_e-S_o\\|_\\infty=\\Theta(1)$ and $\\|S_e-S_o\\|_1=\\Theta(\\sqrt n)$. The proof introduces a partial-deletion process that shifts the middle of the string by a random binomial offset $r$; the difference between the two trace distributions becomes an alternating sum over $r$ of products of binomial coefficients. The paper shows this alternating sum is exponentially small by viewing it as a Fourier transform evaluated at $\\xi=\\pm\\pi$ and bounding the transform with a moment generating function argument. The companion result is an algorithm that identifies deletion-free chunks by looking only at the chunks that bracket them, never at the chunk itself, and then aligns and averages those unbiased chunks to recover a random $S$ to $\\ell_1$ error $\\epsilon$ with polynomially many traces.","pith_inferences":["If the lower-bound machinery generalizes, strings with probabilities restricted to multiples of $1/k$ should interpolate between the exponential hardness proved here and the binary case; the paper leaves this interpolation open, and it could be tested directly with the same Fourier-moment argument.","The same 'estimate only what you did not look at' principle could be applied to other self-referential reconstruction problems; a testable consequence is that one round of localization followed by mapping avoids the bias that iterated localization-mapping schemes accumulate.","An empirical measurement of post-alignment bias would settle whether the average-case algorithm's analysis gap is real: if conditioning on successful alignment shifts the mean of returned chunks by more than $\\epsilon$, the independence step in the proof is not merely unquantified but false.","The Fourier/moment-generating-function technique should transfer to other channels with independent per-coordinate noise, such as substitutions or insertions, where trace distributions also factor as convolutions of per-coordinate transforms."],"forward_implications":["For every constant deletion probability, worst-case generalized trace reconstruction requires $2^{\\Omega(\\sqrt n)}$ traces; the lower bound applies to all algorithms, not just a restricted class.","The hardness begins already at deletion probability $\\delta=\\Omega(1/\\sqrt n)$, so the exponential sample complexity cannot be blamed on a high deletion rate.","Random probability strings are easy: with $\\delta\\le 10^{-7}$, $\\mathrm{poly}(n,1/\\epsilon)$ traces and computation recover $S$ to $\\ell_1$ error $\\epsilon$ with probability at least $1-1/\\mathrm{poly}(n)$.","A polynomial dependence on $n$ and $1/\\epsilon$ is necessary even without deletions, since recovering most coordinates to error $O(\\epsilon/n)$ requires $\\Omega(n^2/\\epsilon^2)$ traces.","Because standard trace reconstruction is the case $p_i\\in\\{0,1\\}$, the worst-case result gives evidence that the super-polynomial hardness of trace reconstruction survives the move from bits to probabilities."],"supporting_citations":[{"why":"Introduces trace reconstruction, the special case where all probabilities are 0 or 1; supplies the baseline model and original question.","marker":"[BKKM04]"},{"why":"Introduces population recovery from the deletion channel; the paper places its lower bound in this line and compares its construction to the binomial-based distributions used there.","marker":"[BCF+19]"},{"why":"Supplies the best known worst-case upper bound for standard trace reconstruction, establishing the gap that the new lower bound sharpens from the other side.","marker":"[Cha21]"},{"why":"Provides an early upper bound and a mean-based lower bound, marking the kind of algorithm-class restriction that the new unrestricted lower bound does not use.","marker":"[HMPW08]"}],"fun_headline_variants":["Worst-case strings need exponentially many traces for deletion","Deletion channel: worst-case strings defeat exponential traces","Random strings recoverable polynomially, worst-case exponentially","Trace reconstruction: worst-case hard, random easy for deletion","Exponential lower bound for worst-case, polynomial for random"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"In the average-case theorem, the load-bearing premise is that after the second algorithm conditions on successful alignment, the coordinates of the returned chunks remain close to independent unbiased estimates of the underlying $p_k$; the paper asserts this without a quantitative bound on the bias introduced by the conditioning.","fun_headline_variants_meta":{"raw":{"variants":["Worst-case strings need exponentially many traces for deletion","Deletion channel: worst-case strings defeat exponential traces","Random strings recoverable polynomially, worst-case exponentially","Trace reconstruction: worst-case hard, random easy for deletion","Exponential lower bound for worst-case, polynomial for random"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000219,"raw_usage":{"total_tokens":1571,"prompt_tokens":1202,"completion_tokens":369,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":818,"completion_tokens_details":{"reasoning_tokens":290}},"tokens_in":818,"tokens_out":369,"duration_ms":3961,"temperature":1.0,"reasoning_tokens":290,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:11:12.170001+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 and Algorithm 2 on a random string with, say, $n=10^5$ and $\\delta=10^{-7}$, and compare the averaged returned estimates for each coordinate with the true $p_k$; if the mean bias after successful alignment exceeds the promised $\\epsilon$ on a non-negligible fraction of coordinates, the unquantified independence step in the proof is wrong and the average-case theorem would not hold as stated.","supporting_citations":[],"review_version":1}