Near-Optimal Trace Reconstruction for Mildly Separated Strings

Allen Liu; Anders Aamand; Shyam Narayanan

Near-Optimal Trace Reconstruction for Mildly Separated Strings

T0 review · 0 major / 5 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 The paper proves that any binary string with zero-runs of length at least $C(\log n)^8$ between consecutive 1s can be reconstructed from $O(n\log n)$ traces in polynomial time, for small constant deletion probability.

desk verdict Genuinely new near-optimal trace reconstruction for separated strings; the proof is intricate but the argument holds up on close reading. read the letter →

arxiv 2411.18765 v1 pith:VHOFYGBO submitted 2024-11-27 cs.DS

Anders Aamand , Allen Liu , Shyam Narayanan This is my paper · ORCID

classification cs.DS

keywords tracereconstructiondeletionchannelL-separatedstringsalignmentalgorithmsamplecomplexitypolynomial-timeCatalannumbersconstantprobability

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

This paper proves that trace reconstruction can be solved with $O(n\log n)$ traces and polynomial time for every $L$-separated binary string with $L \ge C(\log n)^8$, provided the deletion probability $\delta$ is a sufficiently small constant. An $L$-separated string is one in which every two consecutive $1$s are separated by at least $L$ zeros, so the class includes strings with many ones, not just sparse strings. The best known algorithms for arbitrary strings require $\exp(\tilde{O}(n^{1/5}))$ traces, and a simple argument shows $\Omega(n)$ traces are necessary, so the paper's bound is optimal up to a logarithmic factor. The proof reduces reconstruction to a left-to-right alignment procedure and then shows, through a Catalan-number recursion, that the procedure is almost never behind the true alignment.

What carries the argument

The central object is the alignment procedure (Algorithm 1). Given estimates $b_0,\ldots,b_{m-1}$ of the first $m$ zero-run lengths, it scans a trace from left to right and, for each surviving $1$ in the trace, chooses the smallest position $j'$ in the original string such that the observed number of zeros since the previous aligned $1$ matches the estimated cumulative gap $b_{j:j'}$ up to tolerance $C_0\log n\sqrt{b_{j:j'}}$. Choosing the smallest plausible position enforces the 'never ahead' property with probability $1-n^{-10}$ (Lemma 3.1). The harder direction is Lemma 3.2, which bounds how often this greedy choice is behind the true position. Its proof splits the pair of sequences $a$ (true gaps) and $b$ (estimates) into locally similar and locally different stretches: where $a$ and $b$ are similar, a periodic-structure argument shows falling a full period behind has probability at most $(2\delta)^K$; where they differ, the alignment must cross a boundary, and the probability factors into independent subproblems. Those subproblems satisfy a recursion whose coefficients are Catalan numbers, giving $p_k\le 100^{2k-1}C_k\delta^k$ for falling $k$ steps behind.

What would settle it

A concrete check is to compute, by dynamic programming over the random variables $w_i$, the exact probability that the alignment procedure is behind when processing the $m$-th surviving $1$, for two identical strings whose zero-run lengths are all equal to $L=C(\log n)^8$ and with $\delta=1/(3\cdot10^6)$. If that probability exceeds the claimed $200\delta$, Lemma 3.2 is false and the main theorem collapses. Simulating the recursion for $p_k$ and checking $p_k\le 100^{2k-1}C_k\delta^k$ for all $k\le C_2\log n$ would test the paper's core inequality directly.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for a string $x\in\{0,1\}^n$ whose zero-run lengths between consecutive $1$s are all at least $L\ge C(\log n)^8$, and for any deletion probability $\delta\le c_0$ (a small universal constant), an algorithm recovers $x$ exactly with high probability from $N=O(n\log n)$ traces in $\mathrm{poly}(n)$ time. The load-bearing lemma is Lemma 3.2: in the idealized process where only $1$s can be deleted, if every candidate gap length lies in $[L,n]$, then the alignment output $f_m$ satisfies $f_m\ge m$ with probability at least $1-200\delta$. The proof of that lemma gives an amortized recursive bound: whenever a run of deleted $1$s could make the algorithm fall $k$ steps behind, the same structure lets an already-behind algorithm catch up, and the resulting recursion is controlled by Catalan numbers. The full pipeline first learns the number of ones, then obtains crude estimates of every zero-run length by taking medians of aligned trace gaps, and then refines them to exact values by averaging over traces that pass a two-sided forward/backward alignment check.

Load-bearing premise

The entire result rests on the inequality $p_k\le 100^{2k-1}C_k\delta^k$ for the probability that the alignment falls $k$ steps behind, and that inequality is proven only under the assumptions $L\ge C(\log n)^8$ and $\delta\le 1/(3\cdot10^6)$; if it fails for some pair of well-separated sequences, the claimed $O(n\log n)$ guarantee is not established.

Editorial extensions

If this is right

For every input string with $L\ge C(\log n)^8$ and small constant $\delta$, the algorithm outputs the exact string with high probability using $O(n\log n)$ traces and polynomial time.
The $O(n\log n)$ sample complexity is within a logarithmic factor of optimal, because distinguishing two strings with a single $1$ in adjacent positions requires $\Omega(n)$ traces.
The class of strings handled is not sparse: it can contain up to $n/\mathrm{polylog}\, n$ ones, whereas the previous parameterized polynomial-time algorithm needed the number of ones to be polylogarithmic at this separation level.
The pipeline separates coarse median-based estimation from fine averaging-based estimation, with a two-sided alignment check that discards misaligned traces; this is how an alignment event that succeeds only with probability $1-O(\delta)$ is upgraded to an almost-sure event.

Reading between the lines

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

Beyond the paper: the never-ahead/never-behind decomposition is a reusable template. Any alignment clue that is provably never wrong in one direction can be combined with a two-sided check to convert a constant-probability success into a $1-n^{-10}$ event; $L$-separated zero runs are one way to instantiate that template, but the same two-sided verification might transfer to other repetitive string
The exponent $8$ in $(\log n)^8$ is not optimized, and the paper explicitly says its methods will not reach $L=O(\log n)$. An open question it leaves is where the true threshold lies: whether separation $C\log^2 n$ or $C\log n$ already admits a polynomial-time exact algorithm with a different amortization, or whether a new obstruction appears below polylogarithmic separation.
Because the fine phase already discards traces that fail the forward/backward check, a natural weakened variant is approximate reconstruction with fewer traces: instead of averaging enough traces to round to the exact gap, one could stop at a specified edit distance. Prior work achieves $O((\log n)/\varepsilon^2)$ traces for very long runs in the approximate setting; whether the two-sided alignmen

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

Read this one before you sign off on a survey of parameterized trace reconstruction. Aamand, Liu, and Narayanan give the first polynomial-time algorithm that exactly reconstructs an L-separated string (gaps between ones at least C log^8 n) from O(n log n) traces under a small constant deletion probability, matching the Omega(n) information-theoretic lower bound up to a log factor. That is a real step beyond KMMP21, which needed sparsity plus separation, and DRSR21, which only gave approximate reconstruction.

The main technical content is the sequential alignment procedure and its amortized analysis. Lemma 3.1 (never ahead) is straightforward concentration, but Lemma 3.2 (rarely behind) is the heart. I checked the recursive splitting in Lemmas 3.4-3.8, including the Catalan convolution in Lemma 3.8; the constants work, and the special split cases (0,0,0,k) and (0,0,k,0) are handled correctly. The stress-test note agrees, and I didn't find a gap either. The reduction from the actual deletion channel to the simplified process in Section 4 is careful: conditioning on the observed gaps being large is legitimate because L is polylog n and delta is tiny, and the fine estimation's forward/backward certification correctly kills the rare misalignment events.

Soft spots, in proportion. The deletion probability is capped at 1/(3*10^6) and separation must be C log^8 n; the authors openly say they did not optimize constants and don't expect straightforward changes to get delta around 1/2 or L = O(log n). So the practical regime is limited, but that is a boundary of the technique, not an error. The proofs are not machine-checked, and an induction this intricate is exactly where a subtle off-by-one could hide; I found none, but formal verification would raise confidence. There are minor typos: Algorithm 2 says 't equals the number of 0s' (should be 1s), Section 4 says 't-1 ones' (should be t), the case labels in Lemmas 3.5/3.6 are swapped in places, and Algorithm 1's pseudocode assumes the trace contains enough 1s. None of these affect the theorems.

Researchers working on trace reconstruction and deletion channels will want this. Bottom line: it deserves a serious referee. It is a genuine advance for a natural class of hard instances, the proof structure is coherent, and the limitations are stated honestly. I'd send it to peer review; the referee should focus on Lemmas 3.4-3.8 and the independence argument in Lemma 4.4. Reading group? Maybe — the result is exciting enough, but the proof is heavy for a casual session. I'd cite it if I wrote anything nearby in the next year.

Referee Report

0 major / 5 minor

Summary. The paper studies trace reconstruction for L-separated strings, i.e., strings in which the run of zeros between any two consecutive ones has length at least L. The main result, Theorem 1.1, is an algorithm that, for L >= C log^8 n and deletion probability at most a sufficiently small universal constant, reconstructs the string with high probability using O(n log n) independent traces and polynomial time. The algorithm works by maintaining estimates of the gap lengths between consecutive ones and repeatedly aligning retained ones in a trace to ones in the original string. The central technical contribution is an analysis of a probabilistic alignment process in which only ones are deleted: Lemma 3.1 shows the process is never ahead except with probability n^{-10}, and Lemma 3.2 bounds the probability of being behind by 200 delta. The full reconstruction combines a coarse estimation phase using medians, a fine estimation phase using forward and backward alignment with a certification step, and a proof that the certified gap measurements are essentially unbiased.

Significance. If the result is correct, it is a substantial advance: it gives the first polynomial-time, O(n log n)-trace algorithm for a broad class of strings under constant deletion probability, and the O(n log n) sample bound is within a logarithmic factor of the Omega(n) information-theoretic lower bound for distinguishing two adjacent single-one strings. The proofs are self-contained and the constants are fixed up front rather than fitted to the target bound; there is no parameter fitting or circularity. The amortization argument behind Lemma 3.8 is intricate but appears to close, and the reduction from the real deletion channel to the simplified process in Section 4 is carefully argued. The paper also correctly identifies and credits the relation to earlier work on parameterized and approximate trace reconstruction. The main caveats are expository: several typos and notation slips in the central proof sections make the paper harder to verify than it should be.

minor comments (5)

[§3.2 (proof of Lemma 3.2)] In the final case split, the text defines i+r as the first index after i with wi+r = 0, but then conditions on wi+r = wi' = 1 and on f_{i+r}. This is internally inconsistent: f_{i+r} is only defined when wi+r = 1. The intended statement should presumably be that i+r is the first retained index after the initial run of deletions, so that wi+r = 1. As written, this step in the proof of the main alignment lemma cannot be followed, although the surrounding p_{K/2} bound indicates the intended fix.
[§3.2 (Lemmas 3.5 and 3.6)] In the treatment of the special cases, the labels 'former' and 'latter' are swapped relative to the enumeration (0,0,0,k) and (0,0,k,0), and the displayed sums contain repeated variables 'k2,k2' that should be 'k1,k2'. These are presentation errors, but they occur in a delicate induction and should be corrected.
[§3.1 (Lemma 3.1)] The Cauchy-Schwarz step in the proof of Lemma 3.1 appears to omit a square root: the display should have sqrt(|j'-j|) rather than |j'-j| before the bound 4 C1 log n sqrt(b_{j:j'}). With the printed text, the displayed inequality is not valid as written.
[§4.1 (Lemma 4.1)] The phrase 'conditioned on this event holding' should make explicit that the event includes the retention of both the mth and (m+1)th ones; otherwise the claimed conditional distribution of r_{q+1} - r_q - 1 as Bin(a_m, 1-delta) is not guaranteed, since the next retained one may be later if the (m+1)th one is deleted.
[§4 (Algorithms 1–3 and surrounding text)] The pseudocode assumes the trace contains at least t-1 ones when indexing r_q for 1 <= q <= t-1; it should index by the actual number of ones in the given trace. In addition, the text says 'there are t-1 ones' immediately after a depiction with t ones, and Algorithm 2 says 't equals the number of 0s in x' where it should say the number of ones.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the O(n log n) trace guarantee is proven from first principles with fixed constants; no fitted parameter is presented as a prediction.

full rationale

I walked the derivation chain of Theorem 1.1. The main sample-complexity claim is obtained from Theorem 4.4 and Theorem 4.2, which rely on the alignment lemmas Lemma 3.1 and Lemma 3.2. Lemma 3.2 is proved by a self-contained induction over arbitrary sequences a and b (Lemmas 3.4-3.8), with no parameter fitted to the unknown string x, to a dataset, or to the external lower bound. The constants C0, C1, C2, C3, and c0 are fixed in advance; L = C3 log^8 n is an explicit assumption, not a value tuned after seeing traces. The coarse-estimation phase uses the median of gap lengths, and the fine-estimation phase uses forward and backward alignment; in both cases the reported gap is shown to be independent of the centered gap random variable up to an O(n^{-9}) error, so the average is a genuine unbiased estimator rather than a fitted parameter renamed as a prediction. No step of the proof invokes a uniqueness theorem imported from the authors' prior work, and no load-bearing premise is justified only by a self-citation: the self-references (e.g., [Nar21], [NR21]) appear only in related-work context. The paper's explicit caveat that constants were not optimized is a limitation, not a circular step. Overall, the derivation is self-contained against the stated assumptions and external benchmarks, so the circularity score is 0.

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

All constants (C, c0, C0-C3) are universal and chosen in the proof, not fitted to data. The analysis relies on standard concentration, Cauchy-Schwarz, and Catalan number bounds, plus the stated domain assumptions. No invented entities are introduced.

assumptions (4)

domain assumption The deletion channel model: each bit of x is deleted independently with probability delta, and retained bits concatenate in order.
Used throughout; the paper's definition of trace in Section 1.
domain assumption The string x is L-separated with L = C3 log^8 n; all internal zero runs have length at least L.
This is the class of inputs the theorem targets, stated in Theorem 1.1 and Section 2.
standard math Standard concentration inequalities (Chernoff bounds, union bounds) and Cauchy-Schwarz are used without proof.
Invoked in Lemma 3.1, Lemma 3.4, and Section 4.1.
standard math Catalan number identities and growth bounds (Fact 3.7).
Used in Lemma 3.8 to bound the recursion.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Near-Optimal Trace Reconstruction for Mildly Separated Strings." pith.science (2026). https://pith.science/paper/VHOFYGBO

@misc{pith2026241118765,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Trace Reconstruction for Mildly Separated Strings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VHOFYGBO}},
  note         = {Machine review of arXiv:2411.18765}
}

abstract

In the trace reconstruction problem our goal is to learn an unknown string $x\in \{0,1\}^n$ given independent traces of $x$. A trace is obtained by independently deleting each bit of $x$ with some probability $\delta$ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability $\delta$ is constant. The best known upper bound and lower bounds are respectively $\exp(\tilde O(n^{1/5}))$ and $\tilde \Omega(n^{3/2})$ both by Chase [Cha21b,Cha21a]. Our main result is that if the string $x$ is mildly separated, meaning that the number of zeros between any two ones in $x$ is at least polylog$n$, and if $\delta$ is a sufficiently small constant, then the trace reconstruction problem can be solved with $O(n \log n)$ traces and in polynomial time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 32 canonical work pages

[1]

Servedio, and Sandip Sinha

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

work page 2019
[2]

Servedio, and Sandip Sinha

Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha. Efficient average-case population recovery in the presence of insertions and deletions. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques , pages 44:1--44:18, 2019

work page 2019
[3]

Reconstructing strings from random traces

Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Symposium on Discrete Algorithms (SODA) , pages 910--918, 2004

work page 2004
[4]

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 Foundations of Computer Science (FOCS) , 2020

work page 2020
[5]

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). In Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , volume 213 of LIPIcs , pages 11:1--11:23. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2021

work page 2021
[6]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the low deletion rate regime. In Innovations in Theoretical Computer Science (ITCS) , 2021

work page 2021
[7]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. In Symposium on Discrete Algorithms (SODA) , 2021

work page 2021
[8]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Near-optimal average-case approximate trace reconstruction from few traces. In Symposium on Discrete Algorithms (SODA) , 2022

work page 2022

Show all 34 references

[9]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Approximate trace reconstruction from a single trace. In Symposium on Discrete Algorithms (SODA) , 2023

2023
[10]

Coded trace reconstruction

Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and Jo \ a o Ribeiro. Coded trace reconstruction. IEEE Trans. Inf. Theory , 66(10):6084--6103, 2020

2020
[11]

New lower bounds for trace reconstruction

Zachary Chase. New lower bounds for trace reconstruction. Ann. Inst. H. Poincaré Probab. Statist. , 57(2), 2021

2021
[12]

Separating words and trace reconstruction

Zachary Chase. Separating words and trace reconstruction. In Symposium on Theory of Computing (STOC) , 2021

2021
[13]

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. CoRR , abs/2107.06454, 2021

2021 arXiv
[14]

Servedio

Anindya De, Ryan O'Donnell, and Rocco A. Servedio. Optimal mean-based algorithms for trace reconstruction. Annals of Applied Probability , 29(2):851--874, 2019

2019
[15]

Reconstructing trees from traces

Sami Davies, Miklos Racz, and Cyrus Rashtchian. Reconstructing trees from traces. In Conference On Learning Theory (COLT) , pages 961--978, 2019

2019
[16]

R \' a cz, Benjamin G

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

2021
[17]

Trace reconstruction with varying deletion probabilities

Lisa Hartung, Nina Holden, and Yuval Peres. Trace reconstruction with varying deletion probabilities. In Analytic Algorithmics and Combinatorics (ANALCO) , pages 54--61, 2018

2018
[18]

Lower bounds for trace reconstruction

Nina Holden and Russell Lyons. Lower bounds for trace reconstruction. Annals of Applied Probability , 30(2):503--525, 2020

2020
[19]

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 Symposium on Discrete Algorithms (SODA) , pages 389--398, 2008

2008
[20]

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 (COLT) , pages 1799--1840, 2018

2018
[21]

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 International Symposium on Information Theory (ISIT) , pages 297--301, 2005

2005
[22]

Trace reconstruction: Generalized and parameterized

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

2021
[23]

Levenshtein

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

2001
[24]

Levenshtein

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

2001
[25]

Trace reconstruction revisited

Andrew McGregor, Eric Price, and Sofya Vorotnikova. Trace reconstruction revisited. In European Symposium on Algorithms (ESA) , pages 689--700, 2014

2014
[26]

Graph reconstruction from random subgraphs

Andrew McGregor and Rik Sengupta. Graph reconstruction from random subgraphs. In International Colloquium on Automata, Languages, and Programming (ICALP) , volume 229, pages 96:1--96:18, 2022

2022
[27]

Graph reconstruction from noisy random subgraphs

Andrew McGregor and Rik Sengupta. Graph reconstruction from noisy random subgraphs. CoRR , abs/2405.04261, 2024

2024 arXiv
[28]

Improved algorithms for population recovery from the deletion channel

Shyam Narayanan. Improved algorithms for population recovery from the deletion channel. In Symposium on Discrete Algorithms (SODA) , pages 1259--1278. SIAM , 2021

2021
[29]

Trace reconstruction with exp(o(n$ ^ 1/3 $)) samples

Fedor Nazarov and Yuval Peres. Trace reconstruction with exp(o(n$ ^ 1/3 $)) samples. In Symposium on Theory of Computing (STOC) , pages 1042--1046, 2017

2017
[30]

Circular trace reconstruction

Shyam Narayanan and Michael Ren. Circular trace reconstruction. In Innovations in Theoretical Computer Science (ITCS) , 2021

2021
[31]

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 Foundations of Computer Science (FOCS) , pages 228--239, 2017

2017
[32]

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. In International Colloquium on Automata, Languages, and Programming (ICALP) , volume 261 of LIPIcs , pages 102:1--102:20, 2023

2023
[33]

The trace reconstruction problem for spider graphs

Alec Sun and William Yue. The trace reconstruction problem for spider graphs. Discrete Mathematics , 346(1):113115, 2023

2023
[34]

Improved string reconstruction over insertion-deletion channels

Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction over insertion-deletion channels. In Symposium on Discrete Algorithms (SODA) , pages 399--408, 2008

2008

Pith tools

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

[1] [1]

Servedio, and Sandip Sinha

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

work page 2019

[2] [2]

Servedio, and Sandip Sinha

Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha. Efficient average-case population recovery in the presence of insertions and deletions. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques , pages 44:1--44:18, 2019

work page 2019

[3] [3]

Reconstructing strings from random traces

Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Symposium on Discrete Algorithms (SODA) , pages 910--918, 2004

work page 2004

[4] [4]

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 Foundations of Computer Science (FOCS) , 2020

work page 2020

[5] [5]

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). In Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , volume 213 of LIPIcs , pages 11:1--11:23. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2021

work page 2021

[6] [6]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the low deletion rate regime. In Innovations in Theoretical Computer Science (ITCS) , 2021

work page 2021

[7] [7]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. In Symposium on Discrete Algorithms (SODA) , 2021

work page 2021

[8] [8]

Servedio, and Sandip Sinha

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Near-optimal average-case approximate trace reconstruction from few traces. In Symposium on Discrete Algorithms (SODA) , 2022

work page 2022