Quasipolynomial Trace Reconstruction

Arnav Burudgunte; Hongao Wang; Paul Valiant

Quasipolynomial Trace Reconstruction

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Any n-bit string can be recovered from a quasipolynomial number of deletion-channel traces once the retention probability is at least inverse-polylogarithmic.

desk verdict 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. read the letter →

arxiv 2607.04073 v1 pith:L6VNZFUC submitted 2026-07-05 cs.DS cs.ITmath.IT

Arnav Burudgunte , Paul Valiant , Hongao Wang This is my paper · ORCID

classification cs.DScs.ITmath.IT

keywords tracereconstructiondeletionchannelquasipolynomialsamplecomplexityhigher-orderstatisticsFourieranalysismultiplereferencealignmentBLRlinearitytestingbinomialdeconvolution

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

Citations 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.

Referee Report

0 major / 4 minor

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).

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).

minor comments (4)

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.
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.
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.
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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the quasipolynomial bound is obtained from a self-contained inductive argument tracking support size and Fourier decay through explicit lemmas.

full rationale

The derivation chain (base case Lemma 42 from standard mean-based Littlewood bounds, induction step Proposition 36 via Lemmas 15/27/33/35 on abrupt Fourier non-vanishing, triple-product simulation, and binomial deconvolution, culminating in Theorem 43) is analytic and parameter-free. Constants (c', c'' satisfying the explicit inequalities 0.075c' ≥ 3+c and c'c'' ≤ 0.000004) are chosen so that each of the log-log n steps multiplies log(1/τ) by only a constant factor, yielding the final e^{p^{-7/3}(log_2 n)^c} sample complexity by direct calculation. The sole self-citation [BVW26] is used only for motivational contrast (sixth-order statistics for integer sequences) and is not invoked in any load-bearing step of the real-valued induction. No fitted inputs, self-definitional equalities, uniqueness theorems, or renamed empirical patterns appear. The argument is therefore independent of its own conclusions.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The argument rests on standard analytic and probabilistic facts (Fourier inversion, Chernoff bounds, generating functions of binomials, BLR-style linearity testing) plus a collection of carefully chosen universal constants that absorb polynomial losses. No free parameters are fitted to data; the only “parameters” are absolute constants whose existence is proved.

free parameters (2)

universal constant c in the final sample-complexity exponent
Absorbs all the concrete polynomial losses that accumulate over log-log n induction steps; its existence is proved but its numerical value is left unspecified.
various absolute constants appearing in Lemmas 13, 15, 27, 33, 36, 42 (e.g., c, c′, c″, C*)
Chosen large enough so that all Chernoff, Fourier-tail and deconvolution inequalities hold simultaneously; each is proved to exist but not numerically optimized.

assumptions (4)

standard math Standard Fourier analysis on the circle and discrete Fourier transform of finite sequences (Definition 4, Lemmas 10–11).
Used throughout Sections 4–6 to convert product statistics into pointwise products of Fourier transforms.
standard math Chernoff / Hoeffding tail bounds for binomial random variables.
Invoked repeatedly to control left-tail mass of statistics near the first discrepancy and to justify truncation of weight functions.
standard math Littlewood-type lower bounds on polynomials with coefficients in {-1,0,1} (Fact 40 from BE97).
Supplies the base-case mean-based separation (Lemma 42).
domain assumption The deletion channel on a string is equivalent (up to binomial shift) to the deletion channel on a suffix after a random prefix retention (Lemma 5).
The fundamental “zooming” identity that lets the induction move the window start.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quasipolynomial Trace Reconstruction." pith.science (2026). https://pith.science/paper/L6VNZFUC

@misc{pith2026260704073,
  author       = {Pith},
  title        = {Pith review of: Quasipolynomial Trace Reconstruction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L6VNZFUC}},
  note         = {Machine review of arXiv:2607.04073}
}

read the original abstract

We show that trace reconstruction on n-bit strings is possible using a quasipolynomial number of traces, for any retention probability p that is at least inverse polylogarithmic in n.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 3 canonical work pages

[1]

Indiana University mathematics journal , pages=

Littlewood-type problems on subarcs of the unit circle , author=. Indiana University mathematics journal , pages=. 1997 , publisher=

1997
[2]

Random Structures & Algorithms , volume =

Ben-Or, Michael and Coppersmith, Don and Luby, Mike and Rubinfeld, Ronitt , title =. Random Structures & Algorithms , volume =. doi:https://doi.org/10.1002/rsa.20182 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20182 , abstract =

work page doi:10.1002/rsa.20182
[3]

Theory of Computing Systems , volume=

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness , author=. Theory of Computing Systems , volume=. 2016 , publisher=

2016
[4]

1990 , isbn =

Blum, Manuel and Luby, Michael and Rubinfeld, Ronitt , title =. 1990 , isbn =. doi:10.1145/100216.100225 , booktitle =

doi:10.1145/100216.100225 1990
[5]

SIAM Journal on Mathematics of Data Science , volume=

The sample complexity of multireference alignment , author=. SIAM Journal on Mathematics of Data Science , volume=. 2019 , publisher=

2019
[6]

Applied and Computational Harmonic Analysis , volume=

Estimation under group actions: recovering orbits from invariants , author=. Applied and Computational Harmonic Analysis , volume=. 2023 , publisher=

2023
[7]

IEEE Transactions on Information Theory , volume=

Limitations of mean-based algorithms for trace reconstruction at small edit distance , author=. IEEE Transactions on Information Theory , volume=. 2022 , publisher=

2022
[8]

Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Narayanan, Shyam , title =. Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2021 , isbn =

2021

Show all 37 references

[9]

and Sinha, Sandip , booktitle=

Ban, Frank and Chen, Xi and Freilich, Adam and Servedio, Rocco A. and Sinha, Sandip , booktitle=. Beyond Trace Reconstruction: Population Recovery from the Deletion Channel , year=
[10]

Mathematical Statistics and Learning , volume=

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability , author=. Mathematical Statistics and Learning , volume=
[11]

Bulletin of the Australian Mathematical Society , author=

Real. Bulletin of the Australian Mathematical Society , author=. 1983 , pages=. doi:10.1017/S0004972700011515 , number=

1983 doi
[12]

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) , pages=

Circular Trace Reconstruction , author=. 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) , pages=. 2021 , organization=

2021
[13]

IEEE Transactions on Information Theory , volume=

Trace reconstruction: Generalized and parameterized , author=. IEEE Transactions on Information Theory , volume=. 2021 , publisher=

2021
[14]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Reconstructing strings from random traces , author =. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2004 , isbn =

2004
[15]

Annales de l’Institut Henri Poincar

New lower bounds for trace reconstruction , author=. Annales de l’Institut Henri Poincar
[16]

Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

Separating words and trace reconstruction , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=
[17]

IEEE Transactions on Information Theory , volume=

Efficient reconstruction of sequences , author=. IEEE Transactions on Information Theory , volume=. 2002 , publisher=

2002
[18]

2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Beyond trace reconstruction: Population recovery from the deletion channel , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

2019
[19]

IEEE Transactions on Information Theory , volume=

Coded trace reconstruction , author=. IEEE Transactions on Information Theory , volume=. 2020 , publisher=

2020
[20]

2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Coded trace reconstruction in a constant number of traces , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

2020
[21]

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =

Aamand, Anders and Liu, Allen and Narayanan, Shyam , title =. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =. 2025 , volume =

2025
[22]

Knuth , journal =

Donald E. Knuth , journal =. Johann Faulhaber and Sums of Powers , urldate =
[23]

Trace Reconstruction with Constant Deletion Probability and Related Results , booktitle =

Holenstein, Thomas and Mitzenmacher, Michael and Panigrahy, Rina and Wieder, Udi , year =. Trace Reconstruction with Constant Deletion Probability and Related Results , booktitle =
[24]

The Annals of Applied Probability , volume=

Optimal Mean-Based Algorithms for Trace Reconstruction , author=. The Annals of Applied Probability , volume=. 2019 , publisher=

2019
[25]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages =

Nazarov, Fedor and Peres, Yuval , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2017 , isbn =

2017
[26]

2020 , month = apr, journal =

Lower Bounds for Trace Reconstruction , author =. 2020 , month = apr, journal =

2020
[27]

Average-

Peres, Yuval and Zhai, Alex , year =. Average-. 2017

2017
[28]

On k -Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction , year=

Cheng, Kuan and Grigorescu, Elena and Li, Xin and Sudan, Madhu and Zhu, Minshen , booktitle=. On k -Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction , year=
[29]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =

Rivkin, Joey and Valiant, Gregory and Valiant, Paul , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =. 2025 , isbn =

2025
[30]

IEEE Transactions on Information Theory , author =

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance , volume =. IEEE Transactions on Information Theory , author =. 2022 , pages =

2022
[31]

Trace Reconstruction with Bounded Edit Distance , booktitle =

Sima, Jin and Bruck, Jehoshua , year =. Trace Reconstruction with Bounded Edit Distance , booktitle =
[32]

, title =

Chen, Xi and De, Anindya and Lee, Chin Ho and Servedio, Rocco A. , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) , pages =. 2024 , volume =

2024
[33]

17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =

Burudgunte, Arnav and Valiant, Paul and Wang, Hongao , title =. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =. 2026 , volume =

2026
[34]

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages=

Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem , author=. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages=. 2023 , organization=

2023
[35]

Subpolynomial trace reconstruction for random strings

Holden, Nina and Pemantle, Robin and Peres, Yuval , booktitle =. Subpolynomial trace reconstruction for random strings. 2018 , editor =

2018
[36]

and Schiffer, Benjamin G

Davies, Sami and Rácz, Miklós Z. and Schiffer, Benjamin G. and Rashtchian, Cyrus , month = jul, year =. Approximate. 2021. doi:10.1109/ISIT45174.2021.9517926 , abstract =

2021 doi
[37]

and Sinha, Sandip , month = jan, year =

Chen, Xi and De, Anindya and Lee, Chin Ho and Servedio, Rocco A. and Sinha, Sandip , month = jan, year =. Approximate. Proceedings of the 2023. doi:10.1137/1.9781611977554.ch27 , abstract =

2023 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.

[1] [1]

Indiana University mathematics journal , pages=

Littlewood-type problems on subarcs of the unit circle , author=. Indiana University mathematics journal , pages=. 1997 , publisher=

1997

[2] [2]

Random Structures & Algorithms , volume =

Ben-Or, Michael and Coppersmith, Don and Luby, Mike and Rubinfeld, Ronitt , title =. Random Structures & Algorithms , volume =. doi:https://doi.org/10.1002/rsa.20182 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20182 , abstract =

work page doi:10.1002/rsa.20182

[3] [3]

Theory of Computing Systems , volume=

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness , author=. Theory of Computing Systems , volume=. 2016 , publisher=

2016

[4] [4]

1990 , isbn =

Blum, Manuel and Luby, Michael and Rubinfeld, Ronitt , title =. 1990 , isbn =. doi:10.1145/100216.100225 , booktitle =

doi:10.1145/100216.100225 1990

[5] [5]

SIAM Journal on Mathematics of Data Science , volume=

The sample complexity of multireference alignment , author=. SIAM Journal on Mathematics of Data Science , volume=. 2019 , publisher=

2019

[6] [6]

Applied and Computational Harmonic Analysis , volume=

Estimation under group actions: recovering orbits from invariants , author=. Applied and Computational Harmonic Analysis , volume=. 2023 , publisher=

2023

[7] [7]

IEEE Transactions on Information Theory , volume=

Limitations of mean-based algorithms for trace reconstruction at small edit distance , author=. IEEE Transactions on Information Theory , volume=. 2022 , publisher=

2022

[8] [8]

Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Narayanan, Shyam , title =. Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2021 , isbn =

2021