In the trace reconstruction problem , an unknown source string x ∈ {0,1} n is sent through a probabilistic deletion channel that independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x . The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting where x may be an arbitrary string in {0,1} n [ 7 , 8 , 10 , 11 , 12 , 23 ] and in the average-case setting where x is drawn uniformly at random from {0,1} n [ 7 , 8 , 12 , 13 , 25 ]. This article studies trace reconstruction in the smoothed analysis setting, in which a “worst-case” string x worst is chosen arbitrarily from {0,1} n , and then a perturbed version x of x worst is formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstruct x given independent traces from it. Our main result is an algorithm that, for any constant perturbation rate 0< σ < 1 and any constant deletion rate 0 < δ < 1, uses poly( n ) running time and traces and succeeds with high probability in reconstructing the string x . This stands in contrast with the worst-case version of the problem, for which \(\text{exp}(\tilde{O}(n^{1/5}))\) is the best known time and sample complexity [ 8 ]. Our approach is based on reconstructing x from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly( n )-time procedure for reconstructing the multiset of all O (log n )-length subwords of any source string x ∈ {0,1} n given access to traces of x .

The well-known trace reconstruction problem is the problem of inferring an unknown source string x ∈ {0,1}n from independent “traces”, i.e. copies of x that have been corrupted by a δ-deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. The current paper considers the extreme data-limited regime in which only a single trace is provided to the reconstruction algorithm. In this setting exact reconstruction is of course impossible, and the question is to what accuracy the source string x can be approximately reconstructed.

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time $O(n\log n)$, the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS $\ll n$, is still open. We show that for any $n\in\mathbb{N}$ and $\lambda=o(1)$, there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS $\geq\lambda n$, approximates the LIS up to a factor of $1/\lambda^{o(1)}$ in $ n^{o(1)}/\lambda$ time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time; and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of $\Omega(1/\lambda)$, which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from “coarse” (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

In the standard trace reconstruction problem, the goal is to exactly reconstruct an unknown source string x ∊ {0, 1}n from independent “traces”, which are copies of x that have been corrupted by a δ-deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. We study the approximate trace reconstruction problem, in which the goal is only to obtain a high-accuracy approximation of x rather than an exact reconstruction. We give an efficient algorithm, and a near-matching lower bound, for approximate reconstruction of a random source string x ∊ {0, 1}n from few traces. Our main algorithmic result is a polynomial-time algorithm with the following property: for any deletion rate 0 < δ < 1 (which may depend on n), for almost every source string x ∊ {0,1}n, given any number M ≤ Θ(1/δ) of traces from Delδ(x), the algorithm constructs a hypothesis string that has edit distance at most n · (δM)Ω(M) from x. We also prove a near-matching information-theoretic lower bound showing that given M ≤ Θ(1/δ) traces from Delδ(x) for a random n-bit string x, the smallest possible expected edit distance that any algorithm can achieve, regardless of its running time, is n · (δM)O(M).

In the \emph{trace reconstruction problem}, an unknown source string $x \in \{0,1\}^n$ is transmitted through a probabilistic \emph{deletion channel} which independently deletes each bit with some fixed probability $δ$ and concatenates the surviving bits, resulting in a \emph{trace} of $x$. The problem is to reconstruct $x$ given access to independent traces. Trace reconstruction of arbitrary (worst-case) strings is a challenging problem, with the current state of the art for poly$(n)$-time algorithms being the 2004 algorithm of Batu et al. \cite{BKKM04}. This algorithm can reconstruct an arbitrary source string $x \in \{0,1\}^n$ in poly$(n)$ time provided that the deletion rate $δ$ satisfies $δ\leq n^{-(1/2 + \varepsilon)}$ for some $\varepsilon > 0$. In this work we improve on the result of \cite{BKKM04} by giving a poly$(n)$-time algorithm for trace reconstruction for any deletion rate $δ\leq n^{-(1/3 + \varepsilon)}$. Our algorithm works by alternating an alignment-based procedure, which we show effectively reconstructs portions of the source string that are not "highly repetitive", with a novel procedure that efficiently determines the length of highly repetitive subwords of the source string.

In the trace reconstruction problem, an unknown source string x ∊ {0, 1}n is sent through a probabilistic deletion channel which independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x. The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting where x may be an arbitrary string in {0, 1}n [6, 19, 7, 8, 4] and in the average-case setting where x is drawn uniformly at random from {0, 1}n [21, 9, 8, 4]. This paper studies trace reconstruction in the smoothed analysis setting, in which a “worst-case” string xworst is chosen arbitrarily from {0, 1}n, and then a perturbed version x of xworst is formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstruct x given independent traces from it. Our main result is an algorithm which, for any constant perturbation rate 0 < σ < 1 and any constant deletion rate 0 < δ < 1, uses poly(n) running time and traces and succeeds with high probability in reconstructing the string x. This stands in contrast with the worst-case version of the problem, for which the best known sample complexity is exp(Õ(n1/5)) [5], a recent improvement on exp(O(n1/3)) [6, 19]. Our approach is based on reconstructing x from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(n)-time procedure for reconstructing the multiset of all O(log n)-length subwords of any source string x ∊ {0, 1}n given access to traces of x.

A number of recent works have considered the trace reconstruction problem, in which an unknown source string x in {0,1}^n is transmitted through a probabilistic channel which may randomly delete coordinates or insert random bits, resulting in a trace of x. The goal is to reconstruct the original string x from independent traces of x. While the asymptotically best algorithms known for worst-case strings use exp(O(n^{1/3})) traces [De et al., 2017; Fedor Nazarov and Yuval Peres, 2017], several highly efficient algorithms are known [Yuval Peres and Alex Zhai, 2017; Nina Holden et al., 2018] for the average-case version of the problem, in which the source string x is chosen uniformly at random from {0,1}^n. In this paper we consider a generalization of the above-described average-case trace reconstruction problem, which we call average-case population recovery in the presence of insertions and deletions. In this problem, rather than a single unknown source string there is an unknown distribution over s unknown source strings x^1,...,x^s in {0,1}^n, and each sample given to the algorithm is independently generated by drawing some x^i from this distribution and returning an independent trace of x^i. Building on the results of [Yuval Peres and Alex Zhai, 2017] and [Nina Holden et al., 2018], we give an efficient algorithm for the average-case population recovery problem in the presence of insertions and deletions. For any support size 1 <= s <= exp(Theta(n^{1/3})), for a 1-o(1) fraction of all s-element support sets {x^1,...,x^s} subset {0,1}^n, for every distribution D supported on {x^1,...,x^s}, our algorithm can efficiently recover D up to total variation distance at most epsilon with high probability, given access to independent traces of independent draws from D. The running time of our algorithm is poly(n,s,1/epsilon) and its sample complexity is poly (s,1/epsilon,exp(log^{1/3} n)). This polynomial dependence on the support size s is in sharp contrast with the worst-case version of the problem (when x^1,...,x^s may be any strings in {0,1}^n), in which the sample complexity of the most efficient known algorithm [Frank Ban et al., 2019] is doubly exponential in s.

Population recovery is the problem of learning an unknown distribution over an unknown set of n-bit strings, given access to independent draws from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the bit-flip noise channel and for the erasure noise channel. In this paper we initiate the study of population recovery under the deletion channel, in which each bit b is independently deleted with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population is of size 1 (corresponding to a trivial probability distribution supported on a single string) corresponds to the trace reconstruction problem, which is a challenging problem that has received much recent attention. In this work we give algorithms and lower bounds for population recovery under the deletion channel when the population size is some value ℓ > 1. As our main sample complexity upper bound, we show that for any population size ℓ = o(log n / log log n), a population of ℓ strings from {o,1}ncan be learned under deletion channel noise using 2n(1/2+o(1))samples. On the lower bound side, we show that at least nΩ(ℓ)samples are required to perform population recovery under the deletion channel when the population size is ℓ, for all ℓ ≤ n1/2-ε. Our upper bounds are obtained via a robust multivariate generalization of a polynomial-based analysis, due to Krasikov and Roddity [KR97], of how the k-deck of a bit-string uniquely identifies the string; this is a very different approach from recent algorithms for trace reconstruction (the ℓ = 1 case). Our lower bounds build on moment-matching results of Roos[Roos:00] and Daskalakis and Papadimitriou[DP15].

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a reversible preprocessing step that rearranges an n-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis of the bzip compression program. Alas, the decoding process of BWT is inherently sequential and requires Ω(n) time even to retrieve a single character.