Optimal mean-based algorithms for trace reconstruction
Anindya De∗
Northwestern University
anindya@eecs.northwestern.edu

Ryan O’Donnell†
Carnegie Mellon University
odonnell@cs.cmu.edu

arXiv:1612.03148v1 [cs.CC] 9 Dec 2016

Rocco A. Servedio‡
Columbia University
rocco@cs.columbia.edu
December 12, 2016

Abstract
In the (deletion-channel) trace reconstruction problem, there is an unknown n-bit source
string x. An algorithm is given access to independent traces of x, where a trace is formed by
deleting each bit of x independently with probability δ. The goal of the algorithm is to recover x
exactly (with high probability), while minimizing samples (number of traces) and running time.
Previously, the best known algorithm for the trace reconstruction problem was due to Holene 1/2 )) samples and running time for any fixed 0 < δ < 1.
stein et al. [HMPW08]; it uses exp(O(n
It is also what we call a “mean-based algorithm”, meaning that it only uses the empirical means
of the individual bits of the traces. Holenstein et al. also gave a lower bound, showing that any
e
mean-based algorithm must use at least nΩ(log n) samples.
In this paper we improve both of these results, obtaining matching upper and lower bounds
for mean-based trace reconstruction. For any constant deletion rate 0 < δ < 1, we give a meanbased algorithm that uses exp(O(n1/3 )) time and traces; we also prove that any mean-based
algorithm must use at least exp(Ω(n1/3 )) traces. In fact, we obtain matching upper and lower
bounds even for δ subconstant and ρ :=
1 − δ subconstant: when (log3 n)/n ≪ δ ≤ 1/2 the
√
bound is exp(−Θ(δn)1/3 ), and when 1/ n ≪ ρ ≤ 1/2 the bound is exp(−Θ(n/ρ)1/3 ).
Our proofs involve estimates for the maxima of Littlewood polynomials on complex disks.
We show that these techniques can also be used to perform trace reconstruction with random
insertions and bit-flips in addition to deletions. We also find a surprising result: for deletion
probabilities δ > 1/2, the presence of insertions can actually help with trace reconstruction.

∗

Supported by start-up grant from Northwestern University.
Supported by NSF grant CCF-1618679.
‡
Supported by NSF grants CCF-1420349 and CCF-1563155.
†

1

Introduction

Consider a setting in which a string x of length n over an alphabet Σ is passed through a deletion
channel that independently deletes each coordinate of x with probability δ. The resulting string,
of length somewhere between 0 and n, is referred to as a trace of x, or as a received string; the
original string x is referred to as the source string. The trace reconstruction problem is the task of
reconstructing x (with high probability) given access to independent traces of x. This is a natural
and well-studied problem, dating back to the early 2000’s [Lev01b, Lev01a, BKKM04], with some
combinatorial variants dating even to the early 1970’s [Kal73]. However, perhaps surprisingly, much
remains to be discovered both about the information-theoretic and algorithmic complexity of this
problem. Indeed, in a 2009 survey [Mit09, Section 7], Mitzenmacher wrote that “the study of [trace
reconstruction] is still in its infancy”.
Before discussing previous work, we briefly explain why one can assume a binary alphabet
n
without loss of generality. In case of a general Σ, drawing O( log
1−δ ) traces will with high probability
reveal the entire alphabet Σ′ ⊆ Σ of symbols that are present in x. For each symbol σ ∈ Σ′ we may
consider the binary string x|σ whose i-th character is 1 iff xi = σ; a trace of x is easily converted
into a trace of x|σ , so the trace reconstruction problem for x can be solved by solving the binary
trace reconstruction problem for each x|σ and combining the results in the obvious way. For this
reason, our work (and most previous work) focuses on the case of a binary alphabet.

1.1

Prior work

As described in [Mit09], the trace reconstruction problem can arise in several natural domains,
including sensor networks and biology. However, the apparent difficulty of the problem means that
there is not too much published work, at least on the problem of “worst-case” trace reconstruction problem (“worst-case” in the sense that the source string may be any element of {0, 1}n ).
Because of this, several prior authors have considered an “average-case” version of the problem
in which the source string is assumed to be uniformly random over {0, 1}n and the algorithm is
required to succeed with high probability over the random draw of the traces and over the uniform random choice of x. This average-case problem seems to have first been studied by Batu
et al. [BKKM04], who showed that a simple efficient algorithm which they call Bitwise Majority
Alignment succeeds with high probability for sufficiently small deletion rates δ = O(1/ log n) using only O(log n) traces. Subsequent work of Kannan and McGregor [KM05] gave an algorithm
for random x that can handle both deletions and insertions (both at rates O(1/ log2 n) as well as
bit-flips (with constant probability bounded away from 1/2) using O(log n) traces. Viswanathan
and Swaminathan [VS08] sharpened this result by improving the deletion and insertion rates that
can be handled to O(1/ log n). Finally, [HMPW08] gave a poly(n)-time, poly(n)-trace algorithm
for random x that succeeds with high probability for any deletion rate δ that is at most some
sufficiently small absolute constant.
Several researchers have considered, from an information-theoretic rather than algorithmic perspective, various reconstruction problems that are closely related to the (worst-case) trace reconstruction problem. Kalashnik [Kal73] showed that any n-bit string is uniquely specified by its
k-deck, which is the multiset of all its length-k subsequences, when k = ⌊n/2⌋; this result was
√ later
reproved by Manvel et al. [MMS+ 91]. Scott [Sco97] subsequently showed that k = (1+o(1)) n log n
suffices for reconstruction from the k-deck for any x, and simultaneously and independently Kras√
nikov and Roditty [KR97] showed that k = ⌊ 16
n⌋ + 5 suffices. (McGregor et al. observed
7
yields an information-theoretic algorithm using exp(Õ(n1/2 ))
in [MPV14] that the result of [Sco97]p
traces for any deletion rate δ ≤ 1−O( log(n)/n), but did not discuss the running time of such an al1

gorithm.) On the other side, successively larger Ω(log n) lower bounds on the value of k that suffices
for reconstruction of an arbitrary x ∈ {0, 1}n from its k-deck were given by √
Manvel et al. [MMS+ 91]
log n) due to Dudı́k and
Ω(
and Choffrut and Karhumäki [CK97], culminating in a lower bound of 2
Schulman [DS03].
Surprisingly few algorithms have been given for the worst-case trace reconstruction problem
as defined in the first paragraph of this paper. Batu et al. [BKKM04] showed that a variation
of their Bitwise Majority Alignment algorithm succeeds efficiently using O(n log n) traces if the
deletion rate δ is quite low, at most O(1/n1/2+ε ). Holenstein et al. [HMPW08] gave a “meanbased” algorithm (we explain precisely what is meant by such an algorithm later) that runs in time
√
√
exp(Õ( n)) and uses exp(Õ( n)) traces for any deletion rate δ that is bounded away from 1 by a
constant; this is the prior work that is most relevant to our main positive result. [HMPW08] also
log n

gave a lower bound showing that for any δ bounded away from 0 by a constant, at least nΩ( log log n )
traces are required for any mean-based algorithm. Since the result of [HMPW08], several researchers
(such as [Mos13]) have raised the question of finding (potentially inefficient) algorithms which have
a better sample complexity; however, no progress had been made until this work.
One may also ask (as was done in the “open questions” of [Mit09, Section 7]) for trace reconstruction for more general channels, such as those that allow deletions, insertions, and bit-flips.
The only work we are aware of along these lines is that of Andoni et al. [ADHR12], which gives
results for trace reconstruction for average-case words in the presence of insertions, deletions, and
substitutions on a tree.

1.2

Our results

Theorem 1.1 (Deletion channel positive result). There is an algorithm for the trace reconstruction
problem which, for any constant 0 < δ < 1, uses exp(O(n1/3 )) traces and running time.
Theorem 1.1 significantly improves the running time and sample complexity of the [HMPW08]
algorithm, which is exp(Õ(n1/2 )) for fixed constant δ. Furthermore, we can actually extend Theorem 1.1 to the case of δ = o(1) or δ = 1 − o(1); see Theorem 1.3 below.
The algorithm of Theorem 1.1 is a “mean-based” algorithm, meaning that it uses only the
empirical mean of the trace vectors it receives. We prove an essentially matching lower bound for
such algorithms:
Theorem 1.2 (Deletion channel negative result). For any constant 0 < δ < 1, every mean-based
algorithm must use at least exp(Ω(n1/3 )) traces.
As mentioned, we can also treat δ = o(1) and δ = 1 − o(1):
Theorem 1.3 (Deletion channel general matching bounds). The matching bounds in Theorems 1.1
and 1.2 extend as follows: For O(log3 n)/n ≤ δ ≤ 1/2, the matching bound is exp(Θ(δn)1/3 ) (and
for any smaller δ we have a poly(n) upper bound). Writing ρ = 1− δ for the “retention” probability,
for O(1/n1/2 ) ≤ ρ ≤ 1/2 the matching bound is exp(Θ(n/ρ)1/3 ).
For simplicity in the main portion of the paper we consider only the deletion channel and prove
the above results. In Appendix A we consider a more general channel that allows for deletions,
insertions, and bit-flips, and prove the following result, which extends Theorem 1.1 to that more
general channel and includes Theorem 1.1 as a special case.

2

Theorem 1.4 (General channel positive result). Let C be the general channel described in Section A.1 with deletion probability δ = 1 − ρ, insertion probability σ, and bit-flip probability γ/2.
Define
ρ + δσ
r :=
.
1+σ
Then there is an algorithm for C-channel trace reconstruction using samples and running time
bounded by
(
exp(O(n/r)1/3 )
if C/n1/2 ≤ r ≤ 1/2,
1
1
1
, 1−σ
, 1−γ
)·
poly( 1−δ
exp(O((1 − r)n)1/3 ) if O(log3 n)/n ≤ 1 − r ≤ 1/2.
Since some slight technical and notational unwieldiness is incurred by dealing with the more
general channel, we defer the proof of Theorem 1.4 to Appendix A; however, we note here that
the main core of the proof is unchanged from the deletion-only case. We additionally note that, as
discussed in Appendix A, a curious aspect of the upper bound given by Theorem 1.4 is that having
a constant insertion rate can make it possible to perform trace reconstruction in time exp(O(n1/3 ))
even when the deletion rate is much higher than Theorem 1.3 could handle in the absence of
insertions. A possible intuitive explanation for this is that having random insertions could serve to
“smooth out” worst-case instances that are problematic for a deletion-only model.

1.3

Independent and concurrent work

At the time of writing, we have been informed [Per] that Fedor Nazarov and Yuval Peres have independently obtained results that are substantially similar to Theorems 1.1 and 1.2. Also, Elchanan
Mossel has informed us [Mos] that around 2008, Mark Braverman, Avinatan Hassidim and Elchanan
Mossel had independently proven (unpublished) superpolynomial lower bounds for mean-based algorithms.

1.4

Our techniques

For simplicity of discussion, we restrict our focus in this section to the question of upper bounding
the sample complexity of trace reconstruction for the deletion channel, where every bit gets deleted
independently with probability δ. (As discussed above, generalizing the results to channels which
also allow for insertions and flips is essentially a technical exercise that does not require substantially
new ideas.) As we discuss in Section 3.2, an efficient algorithm follows easily from a sample
complexity upper bound via the observation that the minimization problem whose solution yields
a sample complexity upper bound, extends to a slightly larger convex set, and thus one can use
convex (in fact, linear) programming to get an algorithmic result. Hence the technical meat of the
argument lies in upper bounding the sample complexity.
The key enabling idea for our work is to take an analytic view on the combinatorial process
defined by the deletion channel. More precisely, consider two distinct strings x, x′ ∈ {−1, 1}n . A
necessary (and sufficient) condition to upper bound the sample complexity of trace reconstruction
is to lower bound the statistical distance between the two distributions of traces of x versus x′
(let us write C(x) and C(x′ ) to denote these two distributions). Since analyzing the statistical
distance dTV (C(x), C(x′ )) between the distributions C(x) and C(x′ ) turns out to be a difficult task,
we approach it by considering a limited class of statistical tests.
In [HMPW08] the authors consider “mean-based” algorithms; such algorithms correspond to
statistical tests that only use 1-bit marginals of the distribution of the received string. More

3

precisely, for any 1 ≤ j ≤ n, consider the quantities Pry←C(x) [y j = 1] and Pry′ ←C(x′ ) [y ′j = 1]. The
difference |Pry←C(x) [y j = 1] − Pry′ ←C(x′ ) [y ′j = 1]| is a lower bound on dTV (C(x), C(x′ )).
Let us define the vector βx,x′ = (βx,x′ (1), . . . , βx,x′ (n)) ∈ [−1, 1]n by
βx,x′ (j) =

Pr [y ′j = 1] −

y←C(x)

Pr

y ′ ←C(x′ )

[y j = 1].

In this terminology, giving a sample complexity upper bound on mean-based algorithms correspond
to showing a lower bound on minx6=x′ ∈{−1,1}n kβx,x′ k1 . A central idea in this paper is to analyze
kβx,x′ k1 by studying the Z-transform of the vector βx,x′ . More precisely, for z ∈ C, we consider
P
βbx,x′ (z) := nj=1 βx,x′ (j) · z j−1 . Elementary complex analysis can be used to show that
sup |βbx,x′ (z)| ≤ kβx,x′ k1 ≤

|z|=1

√

n · sup |βbx,x′ (z)|.
|z|=1

Thus, for our purposes, it suffices to study sup|z|=1 |βbx,x′ (z)|. By analyzing the deletion channel
and observing that βbx,x′ (z) is a polynomial in z, we are able to characterize this supremum as the

supremum of a certain polynomial (induced by x and x′ ) on a certain disk in the complex plane.
Thus giving a sample complexity upper bound amounts to lower bounding sup|z|=1 |βbx,x′ (z)| across
all polynomials βbx,x′ induced by distinct x, x′ ∈ {−1, 1}n (essentially, across a class of polynomials
closely related to Littlewood polynomials: those polynomials with all coefficients in {−1, 0, 1}).
The technical heart of our sample complexity upper bound is in establishing such a lower bound.
Finally, similar ideas and arguments are used to lower bound the sample complexity of mean-based
algorithms, by upper bounding sup|z|=1 |βbx,x′ (z)| across all polynomials βbx,x′ induced by distinct
x, x′ ∈ {−1, 1}n .

2

Preliminaries and terminology

Throughout this paper we will use two slightly nonstandard notational conventions. Bits will be
written as {−1, 1} rather than {0, 1}, and strings will be indexed starting from 0 rather than 1.
Thus the source string will be denoted x = (x0 , x1 , . . . , xn−1 ) ∈ {−1, 1}n ; this is the unknown string
that the reconstruction algorithm is trying to recover.
We will write C for the channel through which x is transmitted. In the main body of the paper
our main focus will be on the deletion channel C = Delδ , in which each bit of x is independently
δeleted with probability δ < 1. We will also often consider ρ = 1 − δ > 0, the ρetention probability
of each coordinate. In Appendix A we will see that a more general channel that also involves
insertions and bit-flips can be handled in a similar way.
We will use boldface to denote random variables. We typically write y ← C(x) to denote that
y = (y 0 , y 1 , . . . , y n−1 ) is a random trace (or received string or sample), obtained by passing x
through the channel C. Notice the slight inconvenience that the length of y is a random variable
(for the deletion channel this length is always between 0 and n); we denote this length by n.
We define a trace reconstruction algorithm for channel C to be an algorithm with the following
property: for any unknown source string x ∈ {−1, 1}n , when given access to independent strings
y (1) , y (2) , . . . each distributed according to C(x), it outputs x with probability at least (say) 99%.
The sample complexity of the trace reconstruction algorithm is the number of draws from C(x) that
it uses (in the worst case across all x ∈ {−1, 1}n and all draws from C(x)). We are also interested
in the algorithm’s (worst-case) running time.
As mentioned earlier we will use basic complex analysis. The following notation will be useful:
4

C

Notation 2.1. We write Dr (c) for the closed complex disk of radius r centered at c; i.e., {z ∈ :
|z − c| ≤ r}. We write ∂Dr (c) for the boundary of this disk; thus, e.g., ∂D1 (0) = {z ∈ : |z| = 1}
is the complex unit circle.

C

3

Mean traces

We now come to a key definition, that of the mean trace. For now we restrict our focus to C being
the deletion channel Delδ (we consider a more general channel in Appendix A).
Although a random trace y ← Delδ (x) does not have a fixed length, we can simply define the
mean trace of a source string x ∈ {−1, 1}n to be
µDelδ (x) =

E

y←Delδ (x)

[y ′ ] ∈ [−1, 1]n ,

(1)

where y ′ is y padded with zeros so as to be of length exactly n. Here “0” has a natural interpretation
as a “uniformly random bit” (indeed, a trace reconstruction algorithm could always pad deletionchannel traces with random bits by itself, and this would not change the definition of the mean
trace µDelδ (x)).
The following is immediate:

R

n, µ
Proposition 3.1. Viewing the domain of µDelδ as the real
Delδ (x) is a (real-)linear
Pvector space
function of x; that is, each µDelδ (x)j can be written as i ai,j xi for some constants ai,j ∈ .

3.1

R

The mean-based (deletion-channel) trace reconstruction model

One of the most basic things that a trace reconstruction algorithm can do is calculate an empirical
estimate of the mean trace. A simple Chernoff/union bound shows that, with poly(n/ǫ) samples and
time, an algorithm can compute an estimator µ
bDelδ (x) ∈ [−1, 1]n satisfying kb
µDelδ (x) − µDelδ (x)k1 ≤ ǫ
with very high probability. The algorithm might then proceed to base its reconstruction solely on
µ
bDelδ (x), without relying on further traces. We call such algorithms “mean-based trace reconstruction algorithms” (Holenstein et al. [HMPW08] called them algorithms based on “summary
statistics”). We give a formal definition:
Definition 3.2. An algorithm in the mean-based (deletion-channel) trace reconstruction model
works as follows. Given an unknown source string x ∈ {−1, 1}n , the algorithm first specifies a
bDelδ (x) ∈ [−1, +1]n of the mean trace
parameter T ∈ . The algorithm is then given an estimate µ
satisfying
kb
µDelδ (x) − µDelδ (x)k1 ≤ 1/T.
(2)

N

We define the “cost” of this portion of the algorithm to be T . Having been given µ
bDelδ (x), the
algorithm has no further access to x, but may do further “postprocessing” computation involving
µ
bDelδ (x). The algorithm should end by outputting x.

From the above discussion, we see that an algorithm in the mean-based trace reconstruction
model with cost T1 and postprocessing time T2 may be converted into a normal trace reconstruction
algorithm using poly(n, T1 ) samples and poly(n, T1 ) + T2 time.

5

3.2

The complexity of mean-based (deletion-channel) trace reconstruction

As discussed in [HMPW08], the sample complexity of mean-based trace reconstruction is essentially determined by the minimum distance between the mean traces µDelδ (x) and µDelδ (x′ ) of two
distinct source strings x, x′ ∈ {−1, 1}n . Furthermore, one can get an upper bound on the time
complexity of mean-based trace reconstruction if a certain “fractional relaxation” of this minimum
mean trace distance is large. We state these observations from [HMPW08] here, using slightly
different notation.
Definition 3.3. Given n and 0 ≤ δ < 1, we define:
ǫDelδ (n) :=
ǫfrac
Delδ (n) := min

0≤i<n

min

x,x′ ∈{−1,1}n
x6=x′

min

x,x′ ∈[−1,+1]n

xj =x′j ∈{−1,1}∀j<i
xi =−x′i ∈{−1,1}

kµDelδ (x) − µDelδ (x′ )k1 = 2

min

b∈{−1,0,+1}n
b6=0

kµDelδ (x) − µDelδ (x′ )k1 = 2 min

kµDelδ (b)k1 ;
min

d∈[n] b∈{0}d−1 ×{1}×[−1,+1]n−d

kµDelδ (b)k1 .

In both cases, the equality on the right uses Proposition 3.1.
It’s easy to see that in the mean-based trace reconstruction model, it is information-theoretically
possible for an algorithm to succeed if and only if its cost T exceeds 2/ǫDelδ (n). Thus characterizing
the sample complexity of mean-based trace reconstruction essentially amounts to analyzing ǫDelδ (n).
For example, to establish our lower bound Theorem 1.2, it suffices to prove that the ǫDelδ (n) ≤
exp(−Ω(n1/3 )) for constant 0 < δ < 1.
Furthermore, as observed in [HMPW08], given an ǫfrac
Delδ (n)/4-accurate estimate of µDelδ (x), as
well as the ability to compute the linear function µDelδ (x′ ) for any x′ ∈ [−1, +1]n (or even estimate
frac
it to ǫfrac
Delδ (n)/4-accuracy), one can recover x exactly in poly(n, log(1/ǫDelδ (n))) time by solving
1
a sequence of n linear programs. Thus to establish our Theorem 1.1, it suffices to prove that
1/3 )) for constant 0 < δ < 1.
ǫfrac
Delδ (n) ≥ exp(−O(n

3.3

Reduction to complex analysis

Our next important definition is of a polynomial that encodes the components of µC (x) in its
coefficients — kind of a generating function for the channel. We think of its parameter z as a
complex number.
Definition 3.4. Given x ∈ {−1, 1}n and 0 ≤ δ < 1, we define the deletion-channel polynomial
X
PDelδ ,x (z) =
µDelδ (x)j · z j ,
j<n

a polynomial of degree less than n. We extend this definition to x ∈ [−1, +1]n using the linearity
of µDelδ .
We now make the step to elementary complex analysis, by relating the size of a mean trace
difference µDelδ (b) to the maximum modulus of PDelδ ,b (z) on the unit complex circle (or equivalently,
the unit complex disk, by the Maximum Modulus Principle):
If the algorithm “knows” δ it can efficiently compute µDelδ (x′ ) exactly. But even if it doesn’t “know” δ, it can
estimate δ to sufficient accuracy so that µDelδ (x′ ) can be estimated to the necessary accuracy, with no significant
algorithmic slowdown.
1

6

Proposition 3.5. For any b ∈ [−1, 1]n , we have
max |PDelδ ,b (z)| ≤ kµDelδ (b)k1 ≤

z∈∂D1 (0)

√

n max |PDelδ ,b (z)|.
z∈∂D1 (0)

Proof. Recall that µDelδ (b) is the length-n vector of coefficients for the polynomial PDelδ ,b (z). The
lower bound above is immediate from the triangle inequality. For the upper bound, we use
kµDelδ (b)k21 ≤ nkµDelδ (b)k22 = n

avg |PDelδ ,b (z)|2 ≤ n

z∈∂D1 (0)



max |PDelδ ,b (z)|

z∈∂D1 (0)

2

.

Here the first inequality is Cauchy–Schwarz, the equality is an elementary fact about complex
polynomials (or Fourier series), and the final inequality is obvious.
√
Let us reconsider Definition 3.3. As a factor of n is negligible compared to the bounds we
will prove (which are of the shape exp(−Θ(n1/3 )), we may as well analyze maxz∈∂D1 (0) |PDelδ ,b (z)|
rather than kµDelδ (b)k1 in the definition of ǫDelδ (n) and ǫfrac
Delδ (n). We therefore take a closer look
at the deletion-channel polynomial.

4

The deletion-channel polynomial

In this section we compute the deletion-channel polynomial. When the deletion channel is applied
to some source string x, each bit xi is either deleted with probability δ or else is transmitted at
some position j ≤ i in the received string y. Let us introduce (non-independent) random variables
J 0 , . . . , J n−1 , where J i = ⊥ if xi is deleted and otherwise J i is the position in y at which xi is
transmitted. We thus have
X
X X
X X
X
PDelδ ,x (z) =
E [y j ]·z j =
zj ·
Pr[J i = j]xi =
xi ·
Pr[J i = j]z j =
xi ·“ E ”[z J i ].
j<n

y←C(x)

j<n

i<n

i<n

j<n

i<n

Here we put the expectation E in quotation marks because the expression should count 0 whenever
J i = ⊥. Observing that Pr[J i 6= ⊥] equals the retention probability ρ = 1 − δ, if we define the
conditional random variable
e i = (J i | J i 6= ⊥)
J

e i is an
(so J

N-valued random variable), then we have
PDelδ ,x (z) = ρ

X
i<n

e

xi · E[z J i ].

(3)

e i is distributed as Binomial(i, ρ), and letting B 1 , . . . , B i denote independent
Observing that J
Bernoulli random variables with “success” probability ρ, we easily compute
e

E[z J i ] = E[z B 1 +···+B i ] = E[z B 1 ]i = ((1 − ρ) + ρz)i .

Denoting
w = 1 − ρ + ρz,
we conclude that
PDelδ ,x (z) = ρ

X
i<n

7

xi w i .

As z ranges over the unit circle ∂D1 (0), w ranges over the radius-ρ circle ∂Dρ (1 − ρ). Recalling
Definition 3.3 and Proposition 3.5, we are led to consider the following two quantities for 0 < ρ < 1
(note that by the Maximum Modulus Principle, these quantities are unchanged whether the max
is over Dρ (1 − ρ) or ∂Dρ (1 − ρ)):


n−1
κLittlewood (ρ, n) = min
max |P (w)| : P (w) = b0 + b1 w + · · · + bn−1 w
, bi ∈ {0, ±1} not all 0 ,
w∈Dρ (1−ρ)


frac
d
d+1
N
κbounded (ρ, d) = min
max |P (w)| : P (w) = w + bd+1 w
+ · · · + bN w , N ≥ d, bi ∈ D1 (0) .
w∈Dρ (1−ρ)

By the Maximum Modulus Principle, both κLittlewood (ρ, n) and κfrac
bounded (ρ, d) are nondecreasing
functions of 0 < ρ < 1. It’s also easy to see that both are nonincreasing functions of their second
argument for all 0 < ρ < 1 (for κfrac
bounded (ρ, d), consider replacing P (w) by wP (w)) and observe that
|wP (w)| ≤ |P (w)| for all w ∈ Dρ (1 − ρ)). It thus follows that
κfrac
bounded (ρ, d) ≤ κLittlewood (ρ, d).
Our main technical theorems are the following:
Theorem 4.1. There is a universal constant C ≥ 1 such that:
1/3
κfrac
);
bounded (1 − δ, d) ≥ exp(−C(δd)

for 1/d ≤ δ ≤ 1/2,

1/3
).
κfrac
bounded (ρ, d) ≥ exp(−C(d/ρ)

for 1/d1/2 ≤ ρ ≤ 1/2,

Theorem 4.2. There is a universal constant C ≥ 1 such that:
for C(log3 n)/n ≤ δ ≤ 1/2,
for C/n1/2 ≤ ρ ≤ 1/2,

κLittlewood (1 − δ, n) ≤ exp(−Ω(δn)1/3 );

κLittlewood (ρ, n) ≤ exp(−Ω(n/ρ)1/3 ).

By Definition 3.3, Proposition 3.5, and the discussion at the end of Section 3.2, we have that
Theorem 4.2 implies both Theorem 1.2 and the more general sample complexity lower bound
in Theorem 1.3. Regarding the algorithmic upper bounds in Theorems 1.1 and 1.3, again from
Definition 3.3 and Proposition 3.5 we get that


frac
d
d+1
n−1
ǫDelδ (n) ≥ 2ρ · min
max |P (w)| : P (w) = w + bd+1 w
+ · · · + bn−1 w
, bi ∈ [−1, +1]
0≤d<n

≥ 2ρ · min

0≤d<n

w∈Dρ (1−ρ)

κfrac
bounded (ρ, d)

≥ 2ρ · κfrac
bounded (ρ, n).

Thus the upper bounds Theorems 1.1 and 1.3 likewise follow from Theorem 4.1 and the discussion
at the end of Section 3.2. (Note that if δ ≤ O(log3 n)/n, we can always pay the bound for the
larger value δ = Θ(log3 n)/n), which is poly(n).)

5

Proof of Theorem 4.1

We will need the following:
Theorem 5.1. ([BE97], Corollary 3.2, M = 1 case.) Let Q(w) be a polynomial with constant
coefficient 1 and all other coefficients bounded by 1 in modulus. Fix any 0 < θ ≤ π, and let A be
the arc {eit : −θ ≤ t ≤ θ}. Then supw∈A |Q(w)| ≥ exp(−C1 /θ) for some universal constant C1 .
8

We remark that for any 0 < r < 1, Theorem 5.1 holds for the arc A = {reit : −θ ≤ t ≤ θ} with
e
no change in the constant C1 . This is immediate by applying the theorem to Q(w)
= Q(rw).

Proof of Theorem 4.1. Fix d ≥ 2 (else the hypotheses are vacuous) and δ + ρ = 1. We call Case I
when 1/d ≤ δ < 1/2, and we call Case II when 1/d1/2 ≤ ρ ≤ 1/2. Select

 1 1/3 in Case I,
2(δd)
θ=
 ρ 1/3 in Case II.
d

In Case I we have θ ≤ 1/2, and in Case II we have θ ≤ ρ ≤ 1/2.
Let P (w) = wd · Q(w), where Q(w) is a polynomial with constant coefficient 1 and all other
coefficients bounded by 1 in modulus. We need to show
(
exp(−C(δd)1/3 )
in Case I,
(4)
max |P (w)| ≥
w∈Dρ (δ)
exp(−C(d/ρ)1/3 ) in Case II.

In Case I, the ray {reiθ : r > 0} intersects ∂Dρ (δ) at a unique point, call it w0 . In Case II, the
same ray intersects Dρ (δ) twice (this uses θ ≤ ρ); call the point of larger modulus w0 . In either
case, consider the triangle formed in the complex plane by the points 0, δ, and w0 ; it has some
acute angle α at w0 and an angle of θ at 0. By the Law of Sines,
δ
|w0 |
|w0 |
|w0 |
ρ
=
=
=
=
sin θ
sin α
sin(π − θ − α)
sin(θ + α)
sin θ cos α + sin α cos θ
q
=⇒ |w0 | = δ cos θ + ρ cos α = δ cos θ + ρ 1 − ( ρδ )2 sin2 θ ≥ δ(1 − θ 2 ) + ρ(1 − ( ρδ )2 θ 2 ) = 1 − ρδ θ 2 .

(The last inequality used θ ≤ ρ in Case II.) Writing r0 = |w0 |, Theorem 5.1 (and the subsequent
remark) implies that
max |Q(w)| ≥ exp(−C1 /θ) for A = {r0 eit : −θ ≤ t ≤ θ} ⊂ Dρ (δ).
w∈A

(5)

Thus
max |P (w)| ≥ max |P (w)| ≥ r0d ·exp(−C1 /θ) ≥ (1−(δ/ρ)θ 2 )d ·exp(−C1 /θ) ≥ exp(−2(δ/ρ)θ 2 d−C1 /θ)

w∈Dρ (δ)

w∈A

(the last inequality again using θ ≤ ρ in Case II). Substituting in the value of θ yields (4).

5.1

An improved version

Although we don’t need it for our application, we can actually provide a stronger version of the
results in the previous section that is also self-contained — i.e., it does not rely on Borwein and
Erdélyi’s Theorem 5.1. We used that theorem to establish (5); but more strongly than (5), we can
show there exists an arc A ⊂ Dρ (δ) such that
GMw∈A |Q(w)| ≥ exp(−O(1/θ)),
where the left-hand side here denotes the geometric mean of |Q| along A. (Of course, this is at
most the max of |Q| along A.) To keep the parameters simpler, we will assume ρ ≤ 1/3 (this is
9

the more interesting parameter regime anyway, and it is sufficient to yield our Theorem 1.1). Our
alternate arc A will be
A = {1/3 + reit : −θ ≤ t ≤ θ},

where 0 < r < 2/3 is the larger real radius such that 1/3 + re±iθ ∈ ∂Dρ (δ). We remark that still
A ⊂ Dρ (δ), by virtue of θ ≤ ρ ≤ 1/3, and it is not hard to show that the the endpoint of A, call it
w′ = 1/3 + reiθ ∈ ∂Dρ (δ), again satisfies |w′ | ≥ 1 − Ω( ρδ θ 2 ). Thus instead of using Theorem 5.1 as
a black box, we could have completed our proof of Theorem 4.1 using the following:

Theorem 5.2. Let Q(w) be a polynomial with constant coefficient 1 and all other coefficients
in D1 (0). Fix any 0 < θ ≤ π, 0 ≤ r ≤ 2/3, and let A be the arc {1/3 + reit : −θ ≤ t ≤ θ}. Then
GMw∈A (|Q(w)|) ≥ 9/18π/θ .
Our proof will require one standard fact from the theory of “Mahler measures”:
Fact 5.3. Let Q be a complex polynomial and let O be a circle in the complex plane with center c.
Then GMw∈O (|Q(w)|) ≥ |Q(c)|.
Proof.
Q By a linear transformation we may assume O is the unit circle ∂D1 (0). Express Q(w) =
a0 i (w − αi ), where the αi ’s are the roots of Q. Then
Q GMw∈O (|Q(w)|) — known as Q’s Mahler
measure, see e.g. [Smy08] — is exactly equal to |a0 | i∈I |αi |, where I = {i : |αi | ≥ 1}. (Since
GMw∈O (| · |) is multiplicative, this statement follows immediately
from the
Q
Q elementary fact that
GMw∈O (|w − α|) = max{|α|, 1}.) But clearly we have |a0 | i∈I |αi | ≥ |a0 | i |αi | = |Q(0)|.
We can now establish Theorem 5.2:

Proof of Theorem 5.2. Using the bounds on Q’s coefficients we have:
1
for w ∈ D1 (0);
1 − |w|
|Q(1/3)| ≥ 1 − |1/3| − |1/3|2 − · · · = 1/2.
|Q(w)| ≤ 1 + |w| + |w|2 + · · · =

(6)
(7)

Let us apply Fact 5.3 with O = ∂Dr (1/3) ⊃ A, writing A′ for the complementary arc to A in O.
We get
(8)
1/2 ≤ GMw∈O (|Q(w)|) = GMw∈A (|Q(w)|)θ/π · GMw∈A′ (|Q(w)|)1−θ/π .
And by (6) we have

1
1
GM (|Q(w)|) ≤ GM′ ( 1−|w|
) ≤ GM( 1−|w|
)≤

w∈A′

w∈A

w∈O

GM
( 1 ),
w∈∂D2/3 (1/3) 1−|w|

(9)

1
than the points
where the second inequality is because the points w ∈ A only have larger 1−|w|
′
in A , and the third inequality is because increasing the radius of O from r to 2/3 only increases the
1
value of 1−|w|
for points on O. But now for −π < t ≤ π, the point w = 1/3 + (2/3)eit ∈ D2/3 (1/3)

has |w|2 = 1 − 49 (1 − cos t) and hence

1
9
1
q
=
.
≤
1 − |w|
2(1 − cos t)
1 − 1 − 94 (1 − cos t)

Thus
GM

w∈∂D2/3 (1/3)

1
( 1−|w|
) ≤ exp



1
2π

Z



Z π

  9
9
1
ln 2(1−cos
ln(1
−
cos
t)
dt
= 9, (10)
dt
=
exp
−
2π
t)
2
−π
−π
π

the last integral being known. (One can get a much easier integral, with a slightly worse constant,
by lower-bounding 1 − cos t ≥ (2/π 2 )t2 .) Combining (8), (9), (10) yields the theorem.
10

6

Proof of Theorem 4.2

The key ingredient is the following theorem from [BEK99]. (Recall that a Littlewood polynomial
has all nonzero coefficients either −1 or 1.)
Theorem 6.1 ([BEK99], Theorem 3.3). For all k ≥
√ 2 there is a nonzero Littlewood polynomial
Qk of degree at most k satisfying |Qk (t)| ≤ exp(−c0 k) for all real 0 ≤ t ≤ 1. Here c0 > 0 is a
universal constant.
By a simple use of the Hadamard Three-Circle Theorem and Maximum Modulus Principle,
Borwein and Erdélyi proved in [BE97] that the polynomials in Theorem 6.1 establish tightness of
their Theorem 5.1 (up to the constant C1 ). We quote a result that appears within their proof:
Theorem 6.2 ([BE97], in the first proof of Theorem 3.3 in the “special case”, p. 11). There are
universal constants c1 , c2 , c3 > 0 such that the following holds: For all 0 < a ≤ c1 there exists
an integer 2 ≤ k ≤ c2 /a2 such that maxw∈D6a (1) |Qk (w)| ≤ exp(−c3 /a), where Qk is the nonzero
Littlewood polynomial from Theorem 6.1.
Remark 6.3. Actually, Borwein and Erdélyi proved this with an elliptical disk Ea in place of
D6a (1), where Ea has foci at 1 − 8a and 1 and major axis [1 − 14a, 1 + 6a]. It is easy to see that
D6a (1) ⊂ Ea ⊂ D14a (1), so we wrote D6a (1) in Theorem 6.2 for simplicity and because it loses
almost nothing.
We can now prove Theorem 4.2. We state here a slightly more precise version:
Theorem 6.4. Using the notation δ = 1 − ρ, and the notation Exp(t) = exp(c · t) for an unspecified
universal constant c > 0, we have
(
Exp(−(δn)1/3 )
in Case I: C(log3 n)/n ≤ δ ≤ 1/2,
κLittlewood (ρ, n) ≤
Exp(−(n/ρ)1/3 ) in Case II: C/n1/2 ≤ ρ ≤ 1/2,
provided n ≥ n0 . Here n0 , C ≥ 1 are universal constants.
Proof of Theorem 4.2. With C ≥ 1 to be specified later, select
(
C1 /(δn)1/3 in Case I: C(log3 n)/n < δ ≤ 1/2,
a=
C1 (ρ/n)1/3 in Case II: 1/n1/2 < ρ < 1/2,
where C1 ≥ 1 is a universal constant to be specified later. Assuming n0 = n0 (C1 ) is sufficiently
large we get that a ≤ c1 , where c1 is as in Theorem 6.2. Applying that theorem, we obtain
max |Qk (w)| ≤ Exp(−1/a),
w∈A

where A := D6a (1),

k ≤ c2 /a2 < n/2.

(11)

Here the inequality c2 /a2 < n/2 holds in Case I by assuming n0 = n0 (C1 , c2 ) large enough, and in
Case II by taking C1 = C1 (c2 ) large enough. Now define
P (w) = w⌊n/2⌋ · Qk (w),

a nonzero Littlewood polynomial of degree less than n.

We wish to bound
R := Dρ (δ)

max |P (w)|,
w∈R

11

by the expression in the theorem statement. For the points w ∈ R ∩ A, we are done by (11) (and
the fact that |w⌊n/2⌋ | ≤ 1). For the points in w ∈ R \ A, we claim that
|w|2 ≤ 1 − 36 ρδ a2 ≤ exp(−36 ρδ a2 ) ∀w ∈ R \ A.

(12)

Assuming (12), we get
max |P (w)| ≤ max |w|⌊n/2⌋ · max |Qk (w)| ≤ exp(−18 ρδ a2 )⌊n/2⌋ ·(n/2+1) ≤ Exp(−n ρδ a2 )·(n/2+1),

w∈R\A

w∈R\A

w∈R\A

where the factor n/2 + 1 is an upper bound on |Qk (w)| over all of D1 (0) (recall that Qk is a
Littlewood polynomial of degree less than n/2). By inspection, this is sufficient to complete the
proof in both Case I and Case II (in Case I we need to assume C large enough to absorb the factor
of (n/2 + 1)).
It remains to establish (12). For this we first note that ρ > 3a in both Case I and Case II
(Case I is easier to check; for Case II we need to use that C = C(C1 ) is sufficiently large). This in
particular means that R \ A 6= ∅. Writing w0 for either of the intersection points of ∂R and ∂A,
we have maxw∈R\A |w| ≤ |w0 |. Thus it suffices to upper-bound |w0 |2 .
In the complex plane, consider the triangle formed by δ, 1, and w0 . Note that w0 has distance ρ
from δ and distance 6a from 1. Let θ denote the triangle’s angle at δ. By the Cosine Law,
(6a)2 = ρ2 + ρ2 − 2ρ2 cos θ and hence cos θ = 1 − 18a2 /ρ2 . Now consider the triangle formed by δ,
0, and w0 . Its angle at δ is π − θ and the adjacent sides have length δ, ρ. Thus by the Cosine Law,
|w0 |2 = δ2 + ρ2 − 2δρ cos(π − θ) = δ2 + ρ2 + 2δρ cos θ = (δ + ρ)2 − 36δρa2 /ρ2 = 1 − 36 ρδ a2 ,

as needed for (12).

7

Conclusions

A natural direction for future work is to go beyond mean-based algorithms. For example, an efficient
algorithm can estimate the covariances of all pairs of trace bits. If different sources strings lead to
sufficiently different trace-covariances, one could potentially get a more efficient trace reconstruction
algorithm. Analyzing this strategy is equivalent to analyzing a certain problem concerning the
maxima of Littlewood-like polynomials on 2 ; however we could not make any progress on this
problem. It would also be interesting to develop lower bound techniques that apply to a broader
class of algorithms than just mean-based algorithms.
Finally, we mention that the authors have applied the techniques in this paper (specifically, the
technique used in Section 5.1) to several aspects of the population recovery problem. Details will
appear in a forthcoming work.

C

Acknowledgments
The authors would like to thanks the Simons Foundation for sponsoring the symposium on analysis
of Boolean functions where the authors began work on this project. A. D. would like to thank
Aravindan Vijayaraghavan for useful discussions about this problem.

References
[ADHR12] Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, and Sebastien Roch.
Global alignment of molecular sequences via ancestral state reconstruction. Stochastic
Processes and their Applications, 122(12):3852–3874, 2012. 1.1
12

[BE97]

Peter Borwein and Tamás Erdélyi. Littlewood-type polynomials on subarcs of the unit
circle. Indiana University Mathematics Journal, 46(4):1323–1346, 1997. 5.1, 6, 6.2

[BEK99]

Peter Borwein, Tamás Erdélyi, and Géza Kós. Littlewood-type problems on [0, 1].
Proceedings of the London Mathematical Society, 3(79):22–46, 1999. 6, 6.1

[BKKM04] Tuğkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Proceedings of the 15th Annual ACM-SIAM
Symposium on Discrete Algorithms, pages 910–918, 2004. 1, 1.1
[CK97]

Christian Choffrut and Juhani Karhumäki. Combinatorics of words. In Handbook of
Formal Languages, Volume I, pages 329–438. Springer, 1997. 1.1

[DS03]

Miroslav Dudı́k and Leonard Schulman. Reconstruction from subsequences. Journal
of Combinatorial Theory, Series A, 103(2):337–348, 2003. 1.1

[HMPW08] Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. Trace
reconstruction with constant deletion probability and related results. In Proceedings
of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 389–398,
2008. (document), 1.1, 1.2, 1.4, 3.1, 3.2, 3.2
[Jan14]

Svante Janson. Tail bounds for sums of geometric and exponential variables, 2014.
http://www2.math.uu.se/~svante/papers/sjN14.pdf. A.2

[Kal73]

V. V. Kalashnik. Reconstruction of a word from its fragments. Computational
Mathematics and Computer Science (Vychislitel’naya matematika i vychislitel’naya
tekhnika), Kharkov, 4:56–57, 1973. 1, 1.1

[KM05]

Sampath Kannan and Andrew McGregor. More on reconstructing strings from random
traces: Insertions and deletions. In IEEE International Symposium on Information
Theory, pages 297–301, 2005. 1.1, A.1

[KR97]

Ilia Krasikov and Yehuda Roditty. On a reconstruction problem for sequences,. Journal
of Combinatorial Theory, Series A, 77(2):344–348, 1997. 1.1

[Lev01a]

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

[Lev01b]

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

[Mit09]

Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels. Probability Surveys, 6:1–33, 2009. 1, 1.1

[MMS+ 91] Bennet Manvel, Aaron Meyerowitz, Allen Schwenk, Ken Smith, and Paul Stockmeyer.
Reconstruction of sequences. Discrete Mathematics, 94(3):209–219, 1991. 1.1
[Mos]

Elchanan Mossel. Personal communication, October 2016. 1.3

[Mos13]

Elchanan
Mossel.
MSRI
open
problem
session,
2013.
https://www.msri.org/c/document_library/get_file?uuid=4a885484-bcdd-4238-a3da-21c057
1.1

13

[MPV14]

Andrew McGregor, Eric Price, and Sofya Vorotnikova. Trace reconstruction revisited.
In Proceedings of the 22nd Annual European Symposium on Algorithms, pages 689–700,
2014. 1.1

[Per]

Yuval Peres. Personal communication, October 2016. 1.3

[Sco97]

Alexander Scott. Reconstructing sequences. Discrete Mathematics, 175(1):231–238,
1997. 1.1

[Smy08]

Chris Smyth. The Mahler measure of algebraic numbers: A survey. In Number Theory
and Polynomials, pages 322–349. London Mathematical Society Lecture Note Series
352, 2008. 5.1

[VS08]

Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction
over insertion-deletion channels. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 399–408, 2008. 1.1

A

Results on channels that allow insertions, deletions and flips

A.1

Defining the general channel

We now describe the most general channel C that we analyze, which we subsequently refer to as
“the general channel”. As stated earlier, this channel allows for three different types of corruptions:
deletions with probability δ, insertions with probability σ, and bit-flips with probability γ/2. We
comment that for mean-based algorithms, the presence of bit-flips makes hardly any difference;
thus the reader may focus just on the combination of deletions and insertions.
Our definition of this general channel is essentially the same as that of Kannan and McGregor [KM05]. More precisely, for parameters δ, σ, γ ∈ [0, 1), we define how the channel acts on a
single source bit b ∈ {−1, 1}:
1. First, the channel performs “insertions”; i.e., it repeatedly does the operation “with probability σ, transmit a uniformly random bit; with probability 1 − σ, stop”.
2. Having stopped, the channel “deletes” (completes transmission without sending b or −b) with
probability δ.
3. Otherwise (with probability 1 − δ), the channel transmits one more bit: namely, b with
probability 1 − γ/2, or −b with probability γ/2.
As usual, the channel operates on an entire source string x ∈ {−1, 1}n by operating on its individual
bits independently, concatenating the results. That is,
C(x) = C(x0 )C(x1 ) · · · C(xn−1 ) ∈ {−1, 1}∗ .
Of course, if we set σ = γ = 0, we get the deletion channel Delδ that was analyzed in the main
body of the paper.
An alternative description of the channel’s operation on a single bit xi is as follows:


with probability δ,
w
(13)
C(xi ) = (w, a)
with probability (1 − δ) · γ,


(w, xi ) with probability (1 − δ) · (1 − γ),
14

where a ∈ {−1, 1} is a uniformly random bit, and where w ∈ {−1, 1}G is a uniformly random
string of G bits, with G in turn being a Geometric random variable of parameter 1 − σ.2 From this
description one can see that in a received word y ← C(x), each received bit either “comes from a
properly transmitted source bit xi ”, or else is uniformly random. (The probability each xi comes
through is (1 − δ)(1 − γ).) As a consequence, we have that Proposition 3.1 continues to hold for C:
for every j ∈ , the mean value Ey←C(x) [y j ] is a (real-)linear function of x.
Note that when the insertion probability σ is positive, the received word y ← C(x) does not
have an a priori bounded length. This is a minor annoyance can be handled in several different
ways; we choose one way in the next section.

N

A.2

Mean traces for the general channel

We revisit some of our definitions and observations about mean traces from Section 3, in our new
context of the general channel. We begin with (1), the definition of the mean trace. Since the
length of a received word may now be arbitrarily large, the mean trace is now an infinite vector.
We deal with this by truncating it at what we call the “effective trace length bound N ”.
Definition A.1. For the general channel C with linsertion probability
0 ≤ σ < 1, we define the
m
n+ln(1/(1−σ))
1
).
effective trace length bound N = N (σ) to be N = 10 ·
≤ poly(n, 1−σ
1−σ

Definition A.2. For the general channel C and a source string x ∈ {−1, 1}n , we define the idealized
mean trace to be the infinite sequence
µideal
(x) =
C

E

[(y, 0, 0, 0, . . . )] ∈ [−1, +1]N .

y←C(x)

We define just the mean trace to be its truncation to length N :
µC (x) = (µideal
(x)0 , µideal
(x)1 , . . . , µideal
(x)N −1 ) ∈ [−1, +1]N .
C
C
C
Recalling (13), we see that the length n of a received word is stochastically dominated by
(G1 + 1)+ · · · + (Gn + 1), where the Gi ’s are i.i.d. random variables distributed as Geometric(1− σ).
We upper bound this using Janson’s bound on the sum of independent Geometric random variables
(Theorem 2.1 of [Jan14]), noting that his Geometric random variables count the number of “trials”,
which aligns precisely with our (Gi + 1)’s. His bound gives that Pr[n ≥ N + j] ≤ exp(−(N +
j)(1 − σ)/2) for any j ≥ 0, and hence we have the following: for any x ∈ [−1, 1]n ,
kµC (x) − µideal
(x)k1 =
C

∞
X

ℓ=N

|µideal
(x)|ℓ ≤
C

∞
X

ℓ=N

Pr[n ≥ ℓ] =

∞
X
j=0

Pr[n ≥ N + j]

1
4 exp(−N (1 − σ)/2)
= exp(−N (1 − σ)/2) ·
<
1 − exp(−(1 − σ)/2)
1−σ
≤ 4 exp(−n),
by our choice of N .
(14)
The mean-based trace reconstruction model for the general channel. Definition 3.2
has a natural analogue for the general channel: an algorithm in the mean-based general-channel
and is given an estimate µ
bC (x) ∈ [−1, 1]N of the mean
model specifies a cost parameter T ∈

N

2
Here we use the convention that Geometric random variables take values 0, 1, 2, . . . (equal to the number of
“failures”); i.e., Pr[G = t] = σ t (1 − σ) for each t ≥ 0.

15

trace satisfying kb
µC (x) − µC (x)k1 ≤ 1/T. It is clear that an algorithm in the mean-based generalchannel trace reconstruction model with cost T1 and postprocessing time T2 may be converted
1
, T1 ) samples and
into a normal trace reconstruction algorithm using poly(N, T1 ) = poly(n, 1−σ
1
poly(n, 1−σ , T1 ) + T2 time. Note that since we will be studying algorithms with cost T ≪ 2n ,
(x).
by (14) there is no real difference between getting an estimate of µC (x) or of µideal
C

The complexity of mean-based trace reconstruction for the general channel. Regarding
the complexity of mean-based trace reconstruction, for the general channel we define ǫC (n) and
ǫfrac
C (n) in the obvious way, replacing each occurrence of the length-n vector µDelδ (·) in Definition 3.3
with the length-N vector µC (·). As in Section 3.2, to show that trace reconstruction can be
1
, M ) it suffices to show that
performed under the general channel in time poly(N, M ) = poly(n, 1−σ
frac
3
ǫC (n) ≥ 1/M .

Reduction to complex analysis for the general channel. For x ∈ {−1, 1}n the generalchannel polynomial is defined entirely analogously to Definition 3.4:
X
PC,x (z) =
µC (x)j · z j ;
j<N

note that this is a polynomial of degree less than N . This definition extends to x ∈ [−1, +1]n using
the linearity of µC . Similarly, we may define the idealized general-channel “polynomial” by
X
ideal
µideal
(x)j · z j ;
PC,x
(z) =
C

N

j∈

this will actually be a rational function of z.
Entirely analogous to Proposition 3.5, we get that for every b ∈ [−1, 1]n ,
√
max |PC,b (z)| ≤ kµC (b)k1 ≤ N max |PC,b (z)|.
z∈∂D1 (0)

z∈∂D1 (0)

√
1
) is negligible compared to the bounds
Similar to Section 3.3, a factor of N = poly(n, 1−σ
we will prove, so it suffices to analyze maxz∈∂D1 (0) |PC,b (z)| rather than kµC (b)k1 in the definitions
ideal (z) − P (z)| ≤ 2−n for all
of ǫC (n) and ǫfrac
Moreover, since by (14) we have that |PC,b
C,b
C (n).

ideal (z) ; we do this in the next
b ∈ [−1, 1]n and all z ∈ ∂D1 (0), it suffices to analyze maxz∈∂D1 (0) PC,b
subsection.

A.3

Channel polynomial for general channels

We now compute the ideal channel polynomial for the general channel defined in Section A.1, using
the same technique as in Section 4 and recalling the discussion around the alternative channel
description (13). As usual, let ρ = 1 − δ. Let J i be the random variable whose value is ⊥ if xi
is either deleted (probability δ) or is replaced by a random bit (probability (1 − δ) · γ), or else is
the position j such that coordinate xi of the source string ends up in coordinate j in the received
e i denote the random variable J i conditioned on not being ⊥. Since
string y. As before we let J
Pr[J i 6= ⊥] = (1 − δ) · (1 − γ), a derivation identical to that of (3) yields
X
e
ideal
PC,x
(z) = (1 − δ)(1 − γ)
xi · E[z J i ].
(15)
i<n

3
Again, to carry out the linear-programming algorithm, we can either assume that the channel parameters δ, σ,
γ are known to the algorithm, or else they should estimated; we omit the details here.

16

e

To compute E[z J i ], it is straightforward to see that each coordinate xi′ with i′ < i independently
generates a random number of received positions distributed as G+B, where G ∼ Geometric(1 − σ)
and independently B ∼ Bernoulli(ρ). Further, conditioned on xi not being deleted, xi generates a
number of received positions distributed as G + 1, where the final “+1” is for xi (or −xi ) itself.
e i is distributed as
Thus J
G0 + · · · + Gi + B 0 + · · · + B i−1 ,
where the Gk ’s are independent copies of G and the B k ’s are independent copies of B. We therefore
obtain
i
e
E[z J i ] = E[z G ]i+1 · E[z B ]i = E[z G ] · E[z B ] · E[z G ].
Let FG (z) denote E[z G ] and let FB (z) denote E[z B ]. It is easy to calculate that FG (z) =
and we saw earlier that FB (z) = (1 − ρ) + ρz = δ + ρz. For brevity, let us write

1−σ
1−σz ,

(1 − σ) · (δ + ρz)
,
1 − σz
which is a Möbius transformation of z. Thus w ranges over a complex circle as z ranges over
∂D1 (0). More specifically, as z ranges over ∂D1 (0) we have that w ranges over ∂Dr (1 − r), where
w = FG (z)FB (z) =

r=

ρ + δσ
.
1+σ

Plugging this back into (15) using E[z J̃ i ] = FG (z) · wi , we obtain
X
1−σ X
ideal
·
xi · w i .
PC,x
(z) = (1 − δ) · (1 − γ) · FG (z) ·
xi · wi = (1 − γ) · (1 − δ) ·
1 − σz
i<n

i<n

1−σ
frac
We use the bound 1−σz
≥ 1−σ
2 for z ∈ ∂D1 (0). Now by the analysis of κbounded (r, d) given in
Section 4 we get the following algorithmic result for general-channel trace reconstruction, which is
our most general positive result:

Theorem 1.4, restated. Let C be the general channel described in Section A.1 with deletion
probability δ = 1 − ρ, insertion probability σ, and bit-flip probability γ/2. Define

ρ + δσ
.
1+σ
Then there is an algorithm for C-channel trace reconstruction using samples and running time
bounded by
(
exp(O(n/r)1/3 )
if C/n1/2 ≤ r ≤ 1/2,
1
1
1
poly( 1−δ , 1−σ , 1−γ ) ·
exp(O((1 − r)n)1/3 ) if O(log3 n)/n ≤ 1 − r ≤ 1/2.
r :=

Let us make some observations about this result. First, our Theorem 1.1 for the deletion channel
is the special case of Theorem 1.4 obtained by setting σ = γ = 0. Next, for fixed δ,
if δ ≤ 1/2,

if δ ≥ 1/2,

r ranges from 1 − δ down to 1/2 as σ ranges from 0 up to 1;
r ranges from 1 − δ up to 1/2 as σ ranges from 0 up to 1.

The second statement is rather peculiar: it implies that when the deletion rate is high, the ability
to perform trace reconstruction actually improves, the more insertions there are. Indeed, when
we have deletions only, our ability to do trace reconstruction in time exp(O(n1/3 )) is limited to
retention probability ρ ≥ Ω(1). But as soon as the insertion rate σ satisfies σ ≥ Ω(1), we can
do trace reconstruction in time exp(O(n1/3 )) as long as the retention rate ρ = 1 − δ satisfies
ρ ≥ exp(−O(n1/3 )).
17

