A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities

Gregory Valiant; Joey Rivkin; Paul Valiant

REVIEW 2 major objections 4 minor 25 references

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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…

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

arxiv 2412.00674 v1 pith:46M2I5LW submitted 2024-12-01 cs.DS cs.ITmath.IT

Joey Rivkin , Gregory Valiant , Paul Valiant This is my paper · ORCID

classification cs.DScs.ITmath.IT

keywords generalizedtracereconstructiondeletionchannelworst-caselowerboundaverage-casealgorithmFouriertransformmomentgeneratingfunctiontotalvariationdistancerandomprobabilitystrings

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

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

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

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

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

Referee Report

2 major / 4 minor

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.

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 (2)

[Section 3, Lemma 7, Eq. (6)] 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 4, final paragraph of the proof of Theorem 3] 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.

minor comments (4)

[Theorem 2, Theorem 5, and proof of Theorem 5] 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 4, Algorithm 1 parameterization] 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.
[Abstract and Section 1] 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.
[Lemma 8, first display] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is an explicit construction with a Fourier/MGF indistinguishability proof, and the upper bound is an explicit chunk-matching algorithm; neither reduces to its inputs by construction.

full rationale

The paper's two claims are each derived from explicit, self-contained arguments. For the worst-case lower bound (Theorem 2, proved as Theorem 5 in Section 3), the hard strings Se and So are explicitly constructed via scaled binomial probabilities, and the indistinguishability bound is proven by relating the deletion channel to a partial-deletion process, expressing the statistical distance as an alternating sum, and bounding that sum through Fourier transforms, moment generating functions, and log-concavity (Lemmas 6, 7, 8, Fact 9, Lemmas 10-11). No parameter is fitted to the target quantity, and the conclusion that the trace distributions are within e^{-Omega(sqrt n)} total variation distance is not assumed in any input; the hard instance and the bound are both derived. For the average-case upper bound (Theorem 3, Section 4), the algorithm explicitly isolates deletion-free chunks without looking at their contents, and the analysis provides union-bound and Chernoff arguments for matching, chunk availability, and deletion-freeness (Lemmas 12-17). The only recognized weakness is the final paragraph of Section 4, which acknowledges that independence fails after conditioning on successful alignment of Algorithm 2 and then asserts without a quantitative bound that the coordinates are 'close to independent unbiased estimates'; this is a missing quantitive bias argument, not a circularity, since no estimate is fed back as a definition or fitted parameter of the target claim. The paper cites prior trace reconstruction work for context and comparison, but none of those citations is load-bearing for either theorem: the lower bound relies on the paper's own Lemma 7 and the upper bound on its own Algorithm 1/2 analysis. Thus, while the paper may have correctness gaps or unproven analytical steps, there is no step in which a prediction is equivalent to its input by definition, by renaming, or by a self-citation chain.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The paper's claims do not fit any empirical data. Constants such as w=10000 log m, threshold 5w/12, and δ≤10^{-7} are hand-set analysis parameters, and the lower bound construction uses a scaling parameter α chosen to satisfy proof constraints. All other inputs are standard mathematical tools treated as axioms.

free parameters (3)

chunk size w = 10000 log m
Hand-set in Section 4 to make Hoeffding and Chernoff bounds separate aligned from misaligned chunks; not fitted to data, but the polynomial sample complexity depends on this choice.
matching threshold 5w/12
Hand-set between the expected aligned distance w/3 and expected misaligned distance w/2; the separation margin w/12 drives all concentration arguments in Section 4.
deletion probability bound δ ≤ 10^{-7}
Theorem 3 assumes this small constant; the proof uses it to make deletion-free chunks frequent and deletion patterns detectable.

assumptions (6)

standard math Standard Fourier, convolution, moment generating function, Hoeffding, Chernoff, Prekopa-Leindler, and information processing inequality facts.
Used throughout Lemmas 7-8 and 12-17 without proof; these are background tools, not contributions of the paper.
domain assumption p_i drawn iid Uniform[0,1] for Theorem 3
The average-case result only claims success for this random model, not for worst-case strings.
domain assumption δ ≤ 10^{-7} for Theorem 3
The algorithm's analysis requires a sufficiently small constant deletion probability.
domain assumption δ ≥ c/√n for Theorem 5 lower bound
The lower bound is stated for deletion probabilities at least order 1/√n; smaller deletion probabilities are not covered.
domain assumption n odd in the lower bound construction, extended to all n by padding
Section 3 assumes n odd for the symmetry of S_e and S_o; general n follows by trivial padding.
ad hoc to paper α ≤ √n/(4e^2√(2π)) in the hard construction
Scaling parameter chosen so all probabilities remain bounded below 1 and Lemma 7's moment generating function bound applies; it is a proof parameter for the construction, not an empirical fit.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities." pith.science (2026). https://pith.science/paper/46M2I5LW

@misc{pith2026241200674,
  author       = {Pith},
  title        = {Pith review of: A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/46M2I5LW}},
  note         = {Machine review of arXiv:2412.00674}
}

abstract

We introduce the following natural generalization of trace reconstruction, parameterized by a deletion probability $\delta \in (0,1)$ and length $n$: There is a length $n$ string of probabilities, $S=p_1,\ldots,p_n,$ and each "trace" is obtained by 1) sampling a length $n$ binary string whose $i$th coordinate is independently set to 1 with probability $p_i$ and 0 otherwise, and then 2) deleting each of the binary values independently with probability $\delta$, and returning the corresponding binary string of length $\le n$. The goal is to recover an estimate of $S$ from a set of independently drawn traces. In the case that all $p_i \in \{0,1\}$ this is the standard trace reconstruction problem. We show two complementary results. First, for worst-case strings $S$ and any deletion probability at least order $1/\sqrt{n}$, no algorithm can approximate $S$ to constant $\ell_\infty$ distance or $\ell_1$ distance $o(\sqrt n)$ using fewer than $2^{\Omega(\sqrt{n})}$ traces. Second -- as in the case for standard trace reconstruction -- reconstruction is easy for random $S$: for any sufficiently small constant deletion probability, and any $\epsilon>0$, drawing each $p_i$ independently from the uniform distribution over $[0,1]$, with high probability $S$ can be recovered to $\ell_1$ error $\epsilon$ using $\mathrm{poly}(n,1/\epsilon)$ traces and computation time. We show indistinguishability in our lower bound by regarding a complicated alternating sum (comparing two distributions) as the Fourier transformation of some function evaluated at $\pm \pi,$ and then showing that the Fourier transform decays rapidly away from zero by analyzing its moment generating function.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Beyond trace reconstruction: Population recovery from the deletion channel

Frank Ban, Xi Chen, Adam Freilich, Rocco A Servedio, and Sandip Sinha. Beyond trace reconstruction: Population recovery from the deletion channel. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 745--768. IEEE, 2019

work page 2019
[2]

Reconstructing strings from random traces

Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '04, page 910–918, USA, 2004. Society for Industrial and Applied Mathematics

work page 2004
[3]

Coded trace reconstruction in a constant number of traces

Joshua Brakensiek, Ray Li, and Bruce Spang. Coded trace reconstruction in a constant number of traces. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 482--493. IEEE, 2020

work page 2020
[4]

Approximate Trace Reconstruction via Median String (in Average-Case)

Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximate trace reconstruction via median string (in average-case). ArXiv preprint arXiv:2107.09497 , 2021

work page Pith review arXiv 2021
[5]

Polynomial-time trace reconstruction in the smoothed complexity model

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. ACM Transactions on Algorithms (TALG) , 2020

work page 2020
[6]

Near-optimal average-case approximate trace reconstruction from few traces

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Near-optimal average-case approximate trace reconstruction from few traces. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 779--821. SIAM, 2022

work page 2022
[7]

On k-mer-based and maximum likelihood estimation algorithms for trace reconstruction, 2024

Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, and Minshen Zhu. On k-mer-based and maximum likelihood estimation algorithms for trace reconstruction, 2024

work page 2024
[8]

Coded trace reconstruction

Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and Joao Ribeiro. Coded trace reconstruction. IEEE Transactions on Information Theory , 66(10):6084--6103, 2020

work page 2020

Show all 25 references

[9]

New lower bounds for trace reconstruction

Zachary Chase. New lower bounds for trace reconstruction. ArXiv preprint arXiv:1905.03031 , 2019

1905 arXiv
[10]

Separating words and trace reconstruction

Zachary Chase. Separating words and trace reconstruction. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 21--31, 2021

2021
[11]

Approximate trace reconstruction of random strings from a constant number of traces

Zachary Chase and Yuval Peres. Approximate trace reconstruction of random strings from a constant number of traces. ArXiv preprint arXiv:2107.06454 , 2021

2021 arXiv
[12]

Optimal mean-based algorithms for trace reconstruction

Anindya De, Ryan O'Donnell, and Rocco A Servedio. Optimal mean-based algorithms for trace reconstruction. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 1047--1056, 2017

2017
[13]

Approximate trace reconstruction: Algorithms

Sami Davies, Mikl \'o s Z R \'a cz, Benjamin G Schiffer, and Cyrus Rashtchian. Approximate trace reconstruction: Algorithms. In 2021 IEEE International Symposium on Information Theory (ISIT) , pages 2525--2530. IEEE, 2021

2021
[14]

Lower bounds for trace reconstruction

Nina Holden and Russell Lyons. Lower bounds for trace reconstruction. ArXiv preprint arXiv:1808.02336 , 2019

2019 arXiv
[15]

Trace reconstruction with constant deletion probability and related results

Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. Trace reconstruction with constant deletion probability and related results. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , pages 389--398, 2008

2008
[16]

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

Nina Holden, Robin Pemantle, and Yuval Peres. Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. In Conference On Learning Theory , pages 1799--1840. PMLR, 2018

2018
[17]

More on reconstructing strings from random traces: insertions and deletions

Sampath Kannan and Andrew McGregor. More on reconstructing strings from random traces: insertions and deletions. In Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. , pages 297--301. IEEE, 2005

2005
[18]

Trace reconstruction: Generalized and parameterized

Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Trace reconstruction: Generalized and parameterized. IEEE Transactions on Information Theory , 67(6):3233--3250, 2021

2021
[19]

Efficient reconstruction of sequences

Vladimir I Levenshtein. Efficient reconstruction of sequences. IEEE Transactions on Information Theory , 47(1):2--22, 2001

2001
[20]

Efficient reconstruction of sequences from their subsequences or supersequences

Vladimir I Levenshtein. Efficient reconstruction of sequences from their subsequences or supersequences. Journal of Combinatorial Theory, Series A , 93(2):310--332, 2001

2001
[21]

Trace reconstruction with exp (o (n1/3)) samples

Fedor Nazarov and Yuval Peres. Trace reconstruction with exp (o (n1/3)) samples. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 1042--1046, 2017

2017
[22]

Circular trace reconstruction

Shyam Narayanan and Michael Ren. Circular trace reconstruction. ArXiv preprint arXiv:2009.01346 , 2020

2009 arXiv
[23]

Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice

Yuval Peres and Alex Zhai. Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 228--239. IEEE, 2017

2017
[24]

Average-case to (shifted) worst-case reduction for the trace reconstruction problem

Ittai Rubinstein. Average-case to (shifted) worst-case reduction for the trace reconstruction problem. ArXiv preprint arXiv:2207.11489 , 2022

2022 arXiv
[25]

Improved string reconstruction over insertion-deletion channels

Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction over insertion-deletion channels. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , pages 399--408, 2008

2008

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Beyond trace reconstruction: Population recovery from the deletion channel

Frank Ban, Xi Chen, Adam Freilich, Rocco A Servedio, and Sandip Sinha. Beyond trace reconstruction: Population recovery from the deletion channel. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 745--768. IEEE, 2019

work page 2019

[2] [2]

Reconstructing strings from random traces

Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '04, page 910–918, USA, 2004. Society for Industrial and Applied Mathematics

work page 2004

[3] [3]

Coded trace reconstruction in a constant number of traces

Joshua Brakensiek, Ray Li, and Bruce Spang. Coded trace reconstruction in a constant number of traces. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 482--493. IEEE, 2020

work page 2020

[4] [4]

Approximate Trace Reconstruction via Median String (in Average-Case)

Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximate trace reconstruction via median string (in average-case). ArXiv preprint arXiv:2107.09497 , 2021

work page Pith review arXiv 2021

[5] [5]

Polynomial-time trace reconstruction in the smoothed complexity model

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. ACM Transactions on Algorithms (TALG) , 2020

work page 2020

[6] [6]

Near-optimal average-case approximate trace reconstruction from few traces

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Near-optimal average-case approximate trace reconstruction from few traces. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 779--821. SIAM, 2022

work page 2022

[7] [7]

On k-mer-based and maximum likelihood estimation algorithms for trace reconstruction, 2024

Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, and Minshen Zhu. On k-mer-based and maximum likelihood estimation algorithms for trace reconstruction, 2024

work page 2024

[8] [8]

Coded trace reconstruction

Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and Joao Ribeiro. Coded trace reconstruction. IEEE Transactions on Information Theory , 66(10):6084--6103, 2020

work page 2020