{"id":"464fd988-7400-4569-a2d2-2ed33673d728","arxiv_id":"2607.04073","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.5,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Any n-bit string can be reconstructed from exp(p^{-7/3} (log n)^c) independent deletion traces for retention probability p at least inverse-polylogarithmic.","lead":"Trace reconstruction of unknown n-bit strings from random deletions now needs only quasipolynomially many traces whenever the retention probability is inverse-polylog or larger. This nearly closes a decades-old exponential gap and shows that carefully chosen global product statistics can evade known local-query lower bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claim is a complete analytic proof that the induction of Proposition 36, started from the mean-based base case of Lemma 42, yields a statistic of polylog order whose expectation differs by an inverse-quasipolynomial amount after O(log log n) zoom-outs. Every quantitative hypothesis of the induction (support, Fourier decay, abruptness, retention-probability growth) is matched by the corresponding conclusion, and the authors explicitly track the constant-factor optimality required for quasipolynomiality. The only residual risk is an unnoticed constant-factor slip in one of the Fourier or tail bounds; that risk is already acknowledged by the authors and by the reader, and does not rise to a load-bearing objection that would change the ACCEPT verdict. The concrete check above simply re-verifies the single most delicate constant-factor transfer; if it holds, the claim stands.","tokens_in":49826,"tokens_out":532,"duration_ms":6161,"concrete_test":"Independently re-derive the Fourier bound of Lemma 27 (Eq. 11) from the generating function of β_p (Lemma 21) and the projection-slice identity (Lemma 22), then plug the resulting |Â(ξ)| into the deconvolution radius of Corollary 33; verify that the expanded support of A' remains ≤R'P+O(Rp) and that the final discrepancy τ' is still a constant power of τ under the same c',c'' of Eq. 19.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly flags the only place where the quasipolynomial claim could fail: any super-constant loss of support size or Fourier smoothness when going from weight w through the triple-product coefficients A (Lemma 27) and the deconvolution A' (Corollary 33) would make log(1/τ) grow by more than a constant factor per induction step, turning the final sample complexity exponential after log log n steps. The paper itself states this necessity in Section 3 and designs every intermediate lemma (15, 27, 33, 35, 38, 39) to keep both quantities within constant factors of the binomial optimum. The constants are chosen explicitly (c',c'' satisfying 0.075c'≥3+c and c'c''≤0.000004) so that the inequalities close. No hidden super-constant loss is visible in the written bounds; residual risk is only ordinary algebraic error in a long but modular calculation.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that worst-case trace reconstruction of an arbitrary n-bit string is possible from a quasipolynomial number of independent traces under the deletion channel, for any fixed retention probability p > 0. Concretely, Theorem 43 (and the informal theorem on page 1) states that e^{p^{-7/3}(log_2 n)^c} traces suffice for a universal constant c. The argument proceeds by reducing reconstruction to distinguishing an arbitrary pair x, y via an inductive “zoom-out” around their first discrepancy d: a base-case mean-based statistic (Lemma 42) on a polylog-sized window is iteratively converted, via second- and third-order statistics of sequences, multi-trace simulation (Lemma 17), and carefully controlled binomial deconvolution (Corollary 33), into a higher-order statistic that works on the full strings after O(log log n) steps (Proposition 36).","tokens_in":50064,"tokens_out":786,"duration_ms":14711,"significance":"If correct, the result is a major advance: it replaces the previous best upper bound of exp(Õ(n^{1/5})) by a quasipolynomial bound and thereby closes the exponential gap that had persisted for more than a decade. The techniques deliberately evade the local statistical-query barrier of Chase–De–Lee–Servedio by using non-local polylog-order statistics whose locations are free; the modular control of both support size and Fourier decay at every intermediate step (explicitly required for the final complexity to remain quasipolynomial) is a technical contribution of independent interest, with clear links to multiple-reference alignment and BLR-style linearity testing. The sample-complexity claim is essentially optimal among statistical-query algorithms that stay within the present analytic framework, and the paper correctly notes that maximum-likelihood estimation inherits the same sample bound (though not necessarily the same running time).","major_comments":[],"minor_comments":[{"comment":"The constant c that appears in the final exponent is left completely unspecified; a short remark in Section 8 tracking the concrete losses through the O(log log n) iterations (or even a crude numerical upper bound) would make the result more concrete without changing the asymptotic claim.","section":null},{"comment":"In the discussion of running time (page 3 and end of Section 8) it is stated that distinguishing is quasipolynomial-time via dynamic programming while full reconstruction via MLE is not known to be. A one-sentence clarification that the sample-complexity theorem itself does not claim quasipolynomial time for reconstruction would avoid any possible misreading.","section":null},{"comment":"Notation for the retention probability occasionally switches between p and P inside a single induction step (e.g., Proposition 36 and Lemma 38); a consistent convention (or a short glossary) would improve readability of the long inductive argument.","section":null},{"comment":"Several absolute constants (c, c', c'', C* in Lemmas 13, 15, 33, 42, etc.) are introduced with only the inequalities needed for the induction to close; collecting them in a single “parameter table” or appendix would help a reader verify that the chain of inequalities is free of circularity.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is unusually long and technical, but the modular structure and the explicit constant-tracking make it verifiable in principle. I see no reason to doubt the central claim on the basis of the written proofs; residual risk is ordinary algebraic error in a calculation of this length rather than a conceptual gap. The result is clearly of interest to STOC/FOCS/SICOMP-level venues."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the first quasipolynomial upper bound for worst-case trace reconstruction that works for any p that is inverse-polylog or larger. Previous best was exp(Õ(n^{1/5})); the new bound is e^{p^{-7/3}(log n)^c}. That alone makes it worth reading carefully.\n\nWhat is new is the global-statistic machinery. They zoom out around the first discrepancy by iteratively turning a local mean-based distinguisher into a higher-order statistic that survives binomial blurring. The three pieces that make the induction close are (1) a 3-point linearity test on the log-ratio of Fourier transforms of real sequences (Section 4, BLR-inspired but adapted to the continuous setting), (2) abrupt-start Fourier lower bounds after binomial convolution (Lemma 13), and (3) a controlled deconvolution that keeps both support size and Fourier decay within constant factors of the binomial optimum (Section 6). Multi-trace simulation from a single higher-p trace (Lemma 17) lets them turn triple products back into single statistics of order at most 3k. All of this is written with explicit polynomial losses so that after log log n squarings you still have only quasipolynomial sample complexity.\n\nThe soft spot is exactly the one the authors flag in Section 3: every intermediate map (weight w → triple-product coefficients A → deconvolved A') must preserve both domain size and smoothness up to constants. If any step lost a super-constant factor, the final complexity would become exponential. They choose the free constants (c', c'') so the inequalities close, and the written bounds look tight enough. Residual risk is ordinary algebraic slip in a long modular calculation, not a conceptual hole. Runtime is left open for full reconstruction (MLE is quasipolynomial-sample but not obviously quasipolynomial-time); distinguishing is fine.\n\nCitations are clean; the mean-based base case is a careful sharpening of DOS19/PZ17 rather than a black box. This is for anyone working on deletion channels, statistical queries, or multiple-reference alignment. I would send it to referees without hesitation and would cite the bound and the abrupt-start/deconvolution lemmas myself.","headline":"Quasipolynomial upper bound for worst-case trace reconstruction that finally beats the local-SQ barrier; the induction is modular and the constant-factor control is the whole game.","tokens_in":50682,"tokens_out":558,"would_cite":true,"duration_ms":24104,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Any n-bit string can be recovered from a quasipolynomial number of deletion-channel traces once the retention probability is at least inverse-polylogarithmic.","keywords":["trace reconstruction","deletion channel","quasipolynomial sample complexity","higher-order statistics","Fourier analysis","multiple reference alignment","BLR linearity testing","binomial deconvolution"],"falsifier":"Exhibit two n-bit strings whose first discrepancy is at a known location and show that every statistic of polylogarithmic order, when averaged over all binomial shifts of a window of size roughly R^2, has absolute difference smaller than any inverse-quasipolynomial of n for all retention probabilities in a constant-factor range around a fixed p.","tokens_in":50731,"feed_emoji":"🧬","tokens_out":941,"duration_ms":12817,"temperature":0.7,"pith_summary":"The paper proves that an unknown binary string of length n can be reconstructed from only quasipolynomially many independent traces of a deletion channel, provided each bit is retained with probability at least inverse-polylogarithmic in n. Previous algorithms needed exponentially many traces even for constant retention probability; the new bound is e to a power that is a fixed power of the inverse retention times a polylog of n. The argument works by iteratively “zooming out” around the first position where two candidate strings differ, converting a local mean-based statistic into successively more global higher-order statistics that still separate the candidates after binomial blurring. Each zoom roughly squares the window size, so only log-log n steps reach the whole string, and careful control of support size and Fourier decay keeps the sample complexity quasipolynomial rather than exponential. The result also yields a quasipolynomial-time algorithm for distinguishing any two fixed strings.","feed_headline":"Quasipolynomial traces recover any string from deletions","feed_subtitle":"A zoom-out induction turns local means into global statistics, beating the prior exponential barrier","key_machinery":"An induction that starts from a mean-based (order-1) statistic on a polylog-sized window around the first discrepancy and, at each step, produces a new statistic of order at most three times larger whose discrepancy survives binomial blurring over a window whose length is essentially the square of the previous one; the induction is powered by a three-point test on sequences (inspired by BLR linearity testing) together with exact simulation of three independent low-retention traces from one higher-retention trace and controlled binomial deconvolution.","core_discovery":"There exists a constant c such that, for every retention probability p > 0, every n-bit string can be reconstructed from e^{p^{-7/3}(log_2 n)^c} independent traces of the deletion channel that retains each bit independently with probability p.","pith_inferences":["The same three-point Fourier argument may yield quasipolynomial sample complexity for other group-action reconstruction problems (for example, multireference alignment with non-Gaussian noise) once an abrupt-start condition can be enforced.","If the constant-factor losses in support and smoothness can be driven below 1 + ε, the exponent on log n could be made arbitrarily close to the information-theoretic minimum.","The base-case mean statistic already concentrates near the first discrepancy; a tighter location bound might remove the inverse-polylog restriction on p entirely."],"forward_implications":["Maximum-likelihood estimation itself succeeds with quasipolynomially many traces, because it is known to be sample-optimal up to linear factors.","Any pair of strings can be distinguished in quasipolynomial time by dynamic programming on the likelihood of each observed trace.","The same zoom-out technique supplies the first quasipolynomial upper bound that works for every retention probability down to inverse polylogarithmic.","Local statistical-query lower bounds of exp(Ω̃(n^{1/5})) no longer apply, because the algorithm uses non-local products of bits."],"fun_headline_variants":["Quasipolynomial traces reconstruct any n-bit string from deletions","Any string recovered from quasipolynomial deletion-channel traces","Trace reconstruction succeeds with quasipolynomial samples","Deletion traces in quasipolynomial number recover every string","Quasipolynomial samples suffice for full string trace reconstruction"],"cache_read_input_tokens":38272,"weakest_assumption_plain":"Every intermediate weight function and coefficient sequence must preserve both its support length and its Fourier decay up to only constant factors relative to the optimal binomial tradeoff; any super-constant loss in either quantity turns the final sample complexity exponential.","fun_headline_variants_meta":{"raw":{"variants":["Quasipolynomial traces reconstruct any n-bit string from deletions","Any string recovered from quasipolynomial deletion-channel traces","Trace reconstruction succeeds with quasipolynomial samples","Deletion traces in quasipolynomial number recover every string","Quasipolynomial samples suffice for full string trace reconstruction"]},"model":"grok-4.5","effort":"low","cost_usd":0.008218,"raw_usage":{"total_tokens":1755,"prompt_tokens":530,"num_sources_used":0,"completion_tokens":62,"cost_in_usd_ticks":82180000,"prompt_tokens_details":{"text_tokens":530,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1163,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":530,"tokens_out":62,"duration_ms":8350,"temperature":1.0,"reasoning_tokens":1163,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T21:52:01.736852+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit two n-bit strings whose first discrepancy is at a known location and show that every statistic of polylogarithmic order, when averaged over all binomial shifts of a window of size roughly R^2, has absolute difference smaller than any inverse-quasipolynomial of n for all retention probabilities in a constant-factor range around a fixed p.","supporting_citations":[],"review_version":1}