# Trace reconstruction from local statistical queries

Xi Chen
Columbia University
<EMAIL_ADDRESS>Supported by NSF grants CCF-1703925, IIS-1838154,
CCF-2106429 and CCF-2107187. Anindya De
University of Pennsylvania
<EMAIL_ADDRESS>Supported by NSF grants CCF-1926872, CCF-1910534 and
CCF-2045128. Chin Ho Lee
North Carolina State University
<EMAIL_ADDRESS>Work done in part at Harvard University, supported by
Madhu Sudan’s and Salil Vadhan’s Simons Investigator Awards while at Harvard
University. Rocco A. Servedio
Columbia University
<EMAIL_ADDRESS>Supported by NSF grants IIS-1838154, CCF-2106429,
CCF-2211238 and by the Simons Collaboration on Algorithms and Geometry.

###### Abstract

The goal of _trace reconstruction_ is to reconstruct an unknown $n$-bit string
$x$ given only independent random _traces_ of $x$, where a random trace of $x$
is obtained by passing $x$ through a deletion channel. A _Statistical Query_
(SQ) algorithm for trace reconstruction is an algorithm which can only access
statistical information about the distribution of random traces of $x$ rather
than individual traces themselves. Such an algorithm is said to be _$\ell$
-local_ if each of its statistical queries corresponds to an $\ell$-junta
function over some block of $\ell$ consecutive bits in the trace. Since
several — but not all — known algorithms for trace reconstruction fall under
the local statistical query paradigm, it is interesting to understand the
abilities and limitations of local SQ algorithms for trace reconstruction.

In this paper we establish nearly-matching upper and lower bounds on local
Statistical Query algorithms for both worst-case and average-case trace
reconstruction. For the worst-case problem, we show that there is an
$\tilde{O}(n^{1/5})$-local SQ algorithm that makes all its queries with
tolerance $\tau\geq 2^{-\tilde{O}(n^{1/5})}$, and also that any
$\tilde{O}(n^{1/5})$-local SQ algorithm must make some query with tolerance
$\tau\leq 2^{-\tilde{\Omega}(n^{1/5})}$. For the average-case problem, we show
that there is an $O(\log n)$-local SQ algorithm that makes all its queries
with tolerance $\tau\geq 1/\mathrm{poly}(n)$, and also that any $O(\log
n)$-local SQ algorithm must make some query with tolerance $\tau\leq
1/\mathrm{poly}(n).$

##  1 Introduction

In the _trace reconstruction_ problem, the goal is to reconstruct an unknown
string $x\in\\{0,1\\}^{n}$ given access to independent random _traces_ of $x$,
where a random trace of $x$ is a string obtained by passing $x$ through a
deletion channel that independently deletes each bit with probability $\delta$
and concatenates the surviving bits. Trace reconstruction has been a well-
studied problem since the early 2000s [Lev01b, Lev01a, BKKM04], and some
combinatorial variants of the problem were already considered in the 1970s
[Kal73]. Over the past decade, a wide range of algorithmic results and lower
bounds have been established for many variants of the trace reconstruction
problem, including worst-case [MPV14, DOS17, NP17, HL20, Cha21a, Cha21b],
average-case [PZ17, HPP18, HPPZ19, Rub23], and smoothed analysis [CDL+21b]
versions, the low deletion rate regime [CDL+21a], approximate trace
reconstruction [DRRS21, CDK21, CP21, CDL+22], coded trace reconstruction
[CGMR20, BLS20], variants in which different bits of the source string have
different deletion probabilities [HHP18], circular trace reconstruction
[NR21], trace reconstruction on trees [DRR19, BR23], population recovery
variants [BCF+19, Nar20, Nar21], connections to other problems such as mixture
distribution learning [KMMP19], and more [GSZ21, SB21].

The original, and arguably most fundamental, versions of the problem are the
“worst-case” and “average-case” versions with constant deletion rate
$\delta\in(0,1)$. In the worst-case problem the source string $x$ is an
arbitrary (worst-case) element of $\\{0,1\\}^{n}$, and in the average-case
problem the source string $x$ is selected uniformly at random from
$\\{0,1\\}^{n}$; equivalently, an average-case algorithm is only required to
succeed for a $1-o_{n}(1)$ fraction of all $2^{n}$ possible source strings
$x\in\\{0,1\\}^{n}$. These two problems are the focus of our work, so in the
rest of this paper we consider worst-case and average-case trace
reconstruction and we always assume that the deletion rate $\delta$ is an
arbitrary (known) constant in $(0,1)$.

Despite much effort, there are mildly exponential gaps between the best known
upper bounds and lower bounds for both worst-case and average-case trace
reconstruction. Improving on earlier $2^{\tilde{O}(n^{1/2})}$-trace and
$2^{\tilde{O}(n^{1/3})}$-trace algorithms of [HMPW08, DOS17, NP17], in
[Cha21b] Chase gave an algorithm for worst-case trace reconstruction that uses
$2^{\tilde{O}(n^{1/5})}$ traces. The best known lower bound, also due to Chase
[Cha21a], is $\tilde{\Omega}(n^{3/2})$ traces (improving on earlier
$\tilde{\Omega}(n^{5/4})$ and $\Omega(n)$ lower bounds [HL20, BKKM04]). For
the average-case problem, improving on earlier $\exp(O((\log n)^{1/2}))$-trace
and $\exp(O((\log n)^{1/3}))$-trace algorithms [PZ17, HPP18, HPPZ19],
Rubinstein [Rub23] recently gave an $\exp(\tilde{O}((\log n)^{1/5}))$-trace
algorithm. The best known average-case lower bound, due to Chase [Cha21a], is
$\tilde{\Omega}((\log n)^{5/2})$ traces, improving on an earlier
$\tilde{\Omega}((\log n)^{9/4})$ lower bound [HL20].

These substantial gaps naturally suggest the study of restricted classes of
algorithms for trace reconstruction, with the hope that it may be possible to
obtain sharper results. This is the starting point of our work: we propose to
study the trace reconstruction problem from the vantage point of _statistical
query_ algorithms. As our main contribution we obtain fairly sharp upper and
lower bounds on _local_ statistical query algorithms for trace reconstruction,
as described below.

Statistical Query trace reconstruction algorithms. The _Statistical Query_
(SQ) model [Kea98] was first introduced by Kearns as a means to obtain PAC
learning algorithms that can tolerate random classification noise. In the
decades since then, the SQ model has emerged as a major topic of study in its
own right in computational learning theory and related fields such as
differential privacy and optimization. An attractive feature of the SQ model
is that it is powerful enough to capture state-of-the-art algorithms in a
variety of different settings, yet it is also amenable to proving
_unconditional_ lower bounds.

SQ algorithms can only access data through noisy estimates of the expected
values of user-generated query functions. In the context of trace
reconstruction, an SQ oracle takes as input a bounded _query function_
$q:\\{0,1\\}^{n}\to[-1,1]$ and a _tolerance parameter_ $\tau\in(0,1)$ that are
provided by the reconstruction algorithm. It returns a value $\widehat{P}_{q}$
which satisfies $\lvert\widehat{P}_{q}-P_{q}\rvert\leq\tau$, where $P_{q}$ is
the expected value of $q$ on a random trace, i.e. $P_{q}:=\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[q(\boldsymbol{y})].$111Since
the length of each trace is at most $n$, we view each trace $\boldsymbol{y}$
as padded with a suffix of $n-|\boldsymbol{y}|$ zeros, so the argument to $q$
is actually $\boldsymbol{y}0^{n-|\boldsymbol{y}|}$. This is equivalent to
assuming that the $n$-bit source string $x$ is padded with an infinite suffix
of $0$-bits. Thus an SQ algorithm for trace reconstruction does not receive
any actual traces of $x$; rather, it can only use aggregate statistical
information about the overall distribution of traces.

To the best of our knowledge, the current paper is among the first works that
explicitly considers the trace reconstruction problem from the perspective of
statistical queries (see also [CGL+23], which we discuss in more detail
below). However, in hindsight the earliest nontrivial algorithms for worst-
case trace reconstruction [HMPW08, DOS17, NP17] already made it evident that
SQ algorithms — in fact, SQ algorithms which use extremely simple query
functions — could be effective for trace reconstruction. The algorithms of
[HMPW08, DOS17, NP17] all work by using the traces from
$\mathbf{{Del}}_{\delta}(x)$ only to obtain high-accuracy estimates of the $n$
values $\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[\boldsymbol{y}_{i}]$ for
$i\in[n]$ and then doing some subsequent computation on those estimated
values; thus they correspond to SQ algorithms in which each query function is
simply a Boolean dictator function, i.e. a 1-junta. On the other hand, the
highly efficient average-case trace reconstruction algorithms of [PZ17, HPP18,
HPPZ19, Rub23], which use a sub-polynomial number of traces, involve various
“alignment” routines which attempt to identify locations in individual
received traces that correspond to specific locations in the source string.
These algorithms seem to make essential use of individual traces and do not
seem to be compatible with the SQ model. So given that some, but not all,
known trace reconstruction algorithms correspond to SQ algorithms, it is of
interest to study both the abilities and limitations of SQ algorithms for
trace reconstruction.

In this work we consider a natural class of SQ algorithms, which we call
_$\ell$ -local_ SQ algorithms. An $\ell$-local query function
$q:\\{0,1\\}^{n}\to[-1,1]$ is an $\ell$-junta over some $\ell$ consecutive
bits of its input string, i.e. for all $y$, $q$ satisfies
$q(y)=q^{\prime}(y_{i},y_{i+1},\dots,y_{i+\ell-1})$ for some index $i$ and
some function $q^{\prime}:\\{0,1\\}^{\ell}\to[-1,1].$ We say that an algorithm
is an _$\ell$ -local SQ algorithm with tolerance $\tau_{0}$_ if all of its
calls to the SQ oracle are made with $\ell$-local query functions and the
tolerance parameter for each call is at least $\tau_{0}$.

The results of [DOS17, NP17] already show that 1-local SQ algorithms with
tolerance $\tau_{0}=2^{-\tilde{O}(n^{1/3})}$ can successfully perform worst-
case trace reconstruction, and moreover [DOS17, NP17] additionally show that
tolerance $\tau_{0}=2^{-\tilde{\Omega}(n^{1/3})}$ is required for any 1-local
SQ worst-case trace reconstruction algorithm. Thus, in analyzing the abilities
and limitations of $\ell$-local algorithms for trace reconstruction for a
particular value of $\ell$, our goal is to determine the tolerance which is
necessary and sufficient for such algorithms to succeed in worst-case or
average-case trace reconstruction. A simple argument which we give in Section
2.1 shows that any $\ell$-local SQ algorithm (which may be adaptive) using
tolerance $\tau_{0}$ can be converted to a nonadaptive SQ algorithm that makes
at most $n2^{\ell}$ queries, all of which are $\ell$-local “subword” queries
(defined in Section 2.1) of tolerance $\tau_{0}2^{-\ell}$. Moreover, a
standard argument shows that any nonadaptive SQ algorithm which makes $M$
statistical queries, each with tolerance at least $\tau_{0}$, can be simulated
in the obvious way by a standard trace reconstruction algorithm that uses
$\mathrm{poly}(\log M,1/\tau_{0})$ independent traces from
$\mathbf{{Del}}_{\delta}(x).$ Thus, we will be particularly interested in
identifying the value $\ell$ of the locality parameter for which tolerance
(roughly) $2^{-\ell}$ is both necessary and sufficient for trace
reconstruction. As we explain next, our main results do precisely this, for
both worst-case and average-case trace reconstruction.

###  1.1 Our results

We give upper and lower bounds on local SQ algorithms for both worst-case and
average-case trace reconstruction. Our upper and lower bounds match each other
up to fairly small factors for both the worst-case and average-case versions
of the problem.

The worst-case problem. Our main lower bound is the following result, which
gives a lower bound on the tolerance for $n^{1/5}$-local SQ algorithms
performing worst-case trace reconstruction:

######  Theorem 1 (Worst-case lower bound, informal version of Theorem 6).

Fix any constant deletion rate $0<\delta<1$. For
$\ell=\tilde{\Theta}(n^{1/5})$, any $\ell$-local SQ algorithm for worst-case
trace reconstruction must have tolerance
$\tau_{0}=\exp(-\tilde{\Omega}(n^{1/5})).$

Our algorithmic result for the worst-case problem shows that this lower bound
is essentially optimal:

######  Theorem 2 (Worst-case upper bound, informal version of Theorem 15).

Fix any constant deletion rate $0<\delta<1$. There is a
$\tilde{O}(n^{1/5}))$-local SQ algorithm for the worst-case trace
reconstruction problem with tolerance $\tau_{0}=\exp(-\tilde{O}(n^{1/5}))$.

The average-case problem. As mentioned earlier, the state-of-the-art average-
case trace reconstruction algorithms of [PZ17, HPP18, HPPZ19, Rub23] do not
seem to be compatible with the SQ model. Recall that those algorithms use
$2^{O((\log n)^{c})}$ traces, for $c\in\\{1/5,1/3,1/2\\}$, and thus any SQ
analogue of those algorithms would have tolerance $\approx 2^{-O((\log
n)^{c})}$. We show that no $O(\log n)$-local (or even $n^{0.49}$-local) SQ
algorithm for average-case trace reconstruction can succeed with such a coarse
tolerance parameter:

######  Theorem 3 (Average-case lower bound, informal version of Theorem 23).

Fix any constant deletion rate $0<\delta<1$. Any $\ell$-local SQ algorithm for
average-case trace reconstruction must have tolerance
$\tau_{0}\leq\ell/\sqrt{n}.$

Finally, we give an average-case $O(\log n)$-local SQ algorithm that has
inverse polynomial tolerance:

######  Theorem 4 (Average-case upper bound, informal version of Theorem 25).

Fix any constant deletion rate $0<\delta<1$. There is an $O(\log n)$-local SQ
algorithm for average-case trace reconstruction with tolerance
$\tau_{0}=1/\mathrm{poly}(n)$.

Our results can be summarized as follows: As discussed immediately before
Section 1.1, we may say that an $\ell$-local SQ algorithm with tolerance
$\tau_{0}$ has overall complexity $\mathrm{poly}(n2^{\ell},1/\tau_{0})$.
Theorems 1 and 2 together say that the optimal complexity of worst-case local
SQ trace reconstruction is $2^{\tilde{\Theta}(n^{1/5})}$, and Theorems 3 and 4
together say that the optimal complexity of average-case local SQ trace
reconstruction is $n^{\Theta(1)}.$

###  1.2 Discussion and techniques

The worst-case setting. Theorem 1 and Theorem 2 should be contrasted with
recent results of Cheng et al. [CGL+23], which consider a restricted class of
local SQ algorithms known as _$\ell$ -mer based_ algorithms. As defined by
Mazooji and Shomorony [MS23], the _$\ell$ -mer density map_ is a certain
vector of statistics about the frequency of length-$\ell$ subwords222Recall
that a _subword_ of $x$ is a sequence of bits that occur consecutively in $x$,
i.e. $x_{i}x_{i+1}\cdots x_{i+\ell-1}$, whereas a _substring_ of $x$ is a
subsequence of bits that need not occur consecutively, i.e.
$x_{i_{1}}x_{i_{2}}\cdots x_{i_{\ell}}$. of the source string
$x\in\\{0,1\\}^{n}$. [MS23] gave an algorithm which, for constant deletion
rate $0<\delta<1/2$, constructs an $\varepsilon$-accurate (in $\ell_{\infty}$
distance) estimate of the $\ell$-mer density map using
$\mathrm{poly}(n,2^{\ell},1/\varepsilon)$ traces. Cheng et al. [CGL+23]
defined a trace reconstruction algorithm to be _$\ell$ -mer based_ if it only
uses the $\ell$-mer density map of $x$, and observed that the algorithm of
[MS23] (see in particular Lemma 6 of [MS23] and its proof) only uses local
statistical information about traces, and hence is a local SQ algorithm.

The main result of Cheng et al. is a proof that any $n^{1/5}$-mer based
algorithm for worst-case trace reconstruction must have tolerance
$\tau_{0}=2^{-\tilde{\Omega}(n^{1/5})}$. Our Theorem 1 generalizes this result
because it gives a lower bound for the entire class of $n^{1/5}$-local SQ
algorithms, which includes the class of $n^{1/5}$-mer based algorithms by the
results described above. We remark that Theorem 1 also has a shorter and
simpler proof than Theorem 2 of [CGL+23].

At a high-level, we obtain Theorem 1 by a reduction to proving a 1-local SQ
lower bound on $n$-bit source strings that are “gappy.” These are strings in
which every two 1s are separated by $\gg n^{1/5}$ zeros (see Definition 8 for
the precise definition). The intution here is that for a gappy string, any
$n^{1/5}$-bit subword in its traces is very unlikely to contain two 1s, and so
all the useful information is contained in subword queries of Hamming weight
at most 1, which can then be further reduced to 1-bit queries. Then we can
adapt the lower bound arguments in [DOS17] to gappy strings to obtain our
lower bound.

Turning to Theorem 2, Cheng et al. observed that the
$2^{\tilde{O}(n^{1/5})}$-trace algorithm of [Cha21b] for worst-case trace
reconstruction can be interpreted as a $\tilde{O}(n^{1/5})$-mer based
algorithm with tolerance $\tau_{0}=2^{-\tilde{O}(n^{1/5})}$. By the earlier
observation of Cheng et al. mentioned in the first paragraph and the [MS23]
algorithm, which works provided that the deletion rate $\delta$ lies in
$(0,1/2)$, this means that Chase’s algorithm can be expressed as a
$\tilde{O}(n^{1/5})$-local SQ algorithm which has tolerance
$\tau_{0}=2^{-\tilde{O}(n^{1/5})}$ when $\delta\in(0,1/2).$ Our Theorem 15 is
based on a similar observation about Chase’s algorithm, but applied directly
to the local SQ model without going through the notion of $k$-mer statistics.
Our approach is based on techniques and arguments from [CDL+21b]; using these
techniques allows our argument to apply more generally to the entire range of
deletion rates $\delta\in(0,1)$.

Average-case. The average-case lower bound of Theorem 3 is proved using a
fairly simple argument based on “hiding” a bit which might be either 0 or 1 in
the middle of the source string. We turn to the average-case upper bound.

The average-case SQ algorithm described in Theorem 4 is obtained by adapting
an algorithm for _smoothed_ trace reconstruction to the SQ model. The
[CDL+21b] paper gives an algorithm for “smoothed” trace reconstruction, which
is a generalization of the average-case trace reconstruction problem. While
the algorithm of [CDL+21b] only interacts with the input traces by using them
to form empirical estimates of subword frequencies in traces, it is not
trivially an SQ algorithm. This is because the [CDL+21b] algorithm estimates
these subword frequencies across a range of different deletion probabilities
$\delta,\delta+\Delta,\delta+2\Delta,\dots$ up to $(\delta+1)/2.$ In the usual
(non-SQ) trace reconstruction setting where traces are available, it is
trivial to simulate access to $\mathbf{{Del}}_{\delta^{\prime}}(x)$ given
access to $\mathbf{{Del}}_{\delta}(x)$ for any $\delta^{\prime}>\delta$,
simply by drawing $\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)$ and deleting
each bit of $\boldsymbol{y}$ independently with probability
${\frac{1-\delta^{\prime}}{1-\delta}}$. But in the SQ setting, we only have
access to statistical queries of traces drawn from
$\mathbf{{Del}}_{\delta}(x)$ rather than individual traces. We circumvent this
issue by showing that any algorithm that makes $\ell$-local statistical
queries with tolerance $\tau$ to $\mathbf{{Del}}_{\delta^{\prime}}(x)$, for
$\delta^{\prime}>\delta$, can be simulated by an algorithm that makes only
$\ell^{\prime}$-local statistical queries with tolerance $\tau^{\prime}$ to
$\mathbf{{Del}}_{\delta}(x)$, where (roughly speaking)
$\ell^{\prime}\approx\ell/(1-\delta^{\prime})$ and
$\tau^{\prime}=\Theta(\tau).$ With this ingredient in hand, the algorithm of
[CDL+21b] is easily adapted to give Theorem 4.

###  1.3 Future work

Several natural questions suggest themselves for future work. Perhaps the
foremost among these is the following: Given Theorem 2, the current state-of-
the-art unrestricted algorithm for the general worst-case trace reconstruction
problem is an $\tilde{O}(n^{1/5})$-local SQ algorithm. Might it be the case
that this is in fact an optimal algorithm for trace reconstruction? We
currently seem quite far from being able to resolve this (recall that the
state of the art in lower bounds for unrestricted worst-case trace
reconstruction algorithms is only $\tilde{\Omega}(n^{3/2})$ traces [Cha21b]).

A partial step towards answering the above bold question would be to establish
lower bounds on general SQ algorithms for worst-case trace reconstruction,
i.e. SQ algorithms that are not assumed to have bounded locality. It is
difficult to imagine how queries that depend on far-separated portions of an
input trace could be useful, but proving this seems quite challenging.

As a concrete first goal along these lines, a generalization of the notion of
an $\ell$-local SQ is the notion of a _size- $s$_ SQ. A size-$s$ SQ is an SQ
which asks for the expected value of some $s$-junta function
$q^{\prime}(\boldsymbol{y}_{i_{1}},\dots,\boldsymbol{y}_{i_{s}})$ of a random
trace $\boldsymbol{y}$, but unlike an $\ell$-local SQ the input bits of the
junta do not need to form a consecutive block of positions in
$\boldsymbol{y}$. Similar to Lemma 5, a size-$s$ SQ algorithm can be assumed
without loss of generality to use only query functions of the form
$\mathbf{1}\left[y_{i_{1}},\dots,y_{i_{s}}\right]=w$ as $(i_{1},\dots,i_{s})$
ranges over ${[n]\choose s}$ and $w$ ranges over $\\{0,1\\}^{s}$. Even the
following goal appears to be quite challenging:

> Show that any SQ algorithm for the worst-case trace reconstruction problem
> that makes only size-2 queries must have tolerance $\tau=1/n^{\omega(1)}.$

We believe that this is an interesting target problem for future work.

##  2 Preliminaries

Notation. Given integers $a\leq b$ we write $[a:b]$ to denote
$\\{a,\ldots,b\\}$. It will be convenient for us to index a binary string
$x\in\\{0,1\\}^{n}$ using $[0:n-1]$ as $x=(x_{0},\dots,x_{n-1})$. We write
$\ln$ to denote natural logarithm and $\log$ to denote logarithm to the base
2. We write $|x|$ to denote the length of a string $x$.

We denote the set of non-negative integers by $\mathbbm{Z}_{\geq 0}$. We write
$D_{r}(z)$ to denote the closed disk in the complex plane of radius $r$
centered at $z\in\mathbbm{C}$, and $\partial D_{r}(z)$ to denote the circle
which is the boundary of that disk.

Subwords. Fix a string $x\in\\{0,1\\}^{n}$ and an integer $k\in[n]$. A
$k$-subword of $x$ is a (contiguous) subword of $x$ of length $k$, given by
$(x_{a},x_{a+1},\dots,x_{a+k-1})$ for some $a\in[0:n-k]$. Given such a string
$x$ and integers $0\leq a<b\leq n-1$, we write $x[a:b]$ to denote the subword
$(x_{a},x_{a+1},\dots,x_{b})$. For a string $w\in\\{0,1\\}^{k}$, let
$\\#(w,x)$ denote the number of occurrences of $w$ as a subword of $x$.

Distributions. We use bold font letters to denote probability distributions
and random variables, which should be clear from the context. We write
“$\boldsymbol{x}\sim\mathbf{X}$” to indicate that random variable
$\boldsymbol{x}$ is distributed according to distribution $\mathbf{X}$.

Deletion channel and traces. Throughout this paper the parameter $\delta:0<$
$\delta<1$ denotes the _deletion probability_ , and we write $\rho$ to denote
the retention probability $\rho=1-\delta$. Given a string $x\in\\{0,1\\}^{n}$,
we write $\mathbf{{Del}}_{\delta}(x)$ to denote the distribution of the string
that results from passing $x$ through the $\delta$-deletion channel (so the
distribution $\mathbf{{Del}}_{\delta}(x)$ is supported on $\\{0,1\\}^{\leq
n}$), and we refer to a string drawn from $\mathbf{{Del}}_{\delta}(x)$ as a
_trace_ of $x$. Recall that a random trace
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)$ is obtained by independently
deleting each bit of $x$ with probability $\delta$ and concatenating the
surviving bits. 333For simplicity in this work we assume that the deletion
probability $\delta$ is known to the reconstruction algorithm.

For $x\in\\{0,1\\}^{n}$ (recall that we index the bits of $x$ as
$(x_{0},\dots,x_{n-1}$)) we view a draw of a trace
$\boldsymbol{y}\sim\mathbf{{Del}}(x)$ as corresponding to a $\rho$-biased
random draw of a subset $\mathbf{R}\subseteq[0:n-1]$, where the elements of
$\mathbf{R}$ are the bits that are _retained_ in $x$ to obtain
$\boldsymbol{y}$. So if the sorted elements of $\mathbf{R}$ are
$\mathbf{R}=\\{\boldsymbol{r}_{0}<\boldsymbol{r}_{1}<\cdots<\boldsymbol{r}_{\boldsymbol{m}-1}\\}$
for some $\boldsymbol{m}\leq n$, then the bits of the trace
$\boldsymbol{y}=(\boldsymbol{y}_{0},\boldsymbol{y}_{1},\dots,\boldsymbol{y}_{\boldsymbol{m}-1})$
are
$\boldsymbol{y}_{0}=x_{\boldsymbol{r}_{0}},\boldsymbol{y}_{1}=x_{\boldsymbol{r}_{1}},$
and so on.

###  2.1 Local Statistical Query algorithms

As described earlier, an $\ell$-local query function
$q:\\{0,1\\}^{n}\to[-1,1]$ is a function

$q(y)=q^{\prime}(y_{i},y_{i+1},\dots,y_{i+\ell-1})$

for some index $i$ and some function $q^{\prime}:\\{0,1\\}^{\ell}\to[-1,1],$
i.e. a real-valued bounded $\ell$-junta over consecutive input variables. An
algorithm is an _$\ell$ -local SQ algorithm with tolerance $\tau_{0}$_ if all
of its calls to the SQ oracle are made with $\ell$-local query functions and
the tolerance parameter for each call is at least $\tau_{0}$.

Let us say that an $\ell$-local query function is a _subword query_ if it is
of the form

$q^{\prime}(y)=\mathbf{1}\left[(y_{i},\dots,y_{i+\ell-1})=w\right]$ (1)

for some string $w\in\\{0,1\\}^{\ell}$. The following simple lemma shows that
without loss of generality, every $\ell$-local SQ algorithm makes at most
$n2^{\ell}$ (non-adaptive) queries, corresponding to all possible
length-$\ell$ subword queries:

######  Lemma 5.

Let $A$ be an $\ell$-local SQ algorithm with tolerance $\tau_{0}$ (note that
$A$ may make any number of calls to the SQ oracle and may be adaptive, i.e.
the choice of later queries may depend on the responses received on earlier
queries). Then there is an algorithm $A^{\prime}$ with the same behavior as
$A$ which makes $n2^{\ell}$ queries (all possible length-$\ell$ subword
queries), each with tolerance $\tau_{0}/2^{\ell}.$

###### Proof.

The algorithm $A^{\prime}$ makes all $n2^{\ell}$ subword queries of the form
given in Equation 1, where $i$ ranges over $[n]$ and $w$ ranges over
$\\{0,1\\}^{\ell}$. It makes each such subword query with tolerance parameter
$\tau_{0}/2^{\ell}$. Let $p_{i,w}=\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}(x)}[(\boldsymbol{y}_{i},\dots,\boldsymbol{y}_{i+\ell-1})=w]$
and let $\widehat{p}_{i,w}$ be the value received from the SQ oracle in
response to the query (1), so
$|\widehat{p}_{i,w}-p_{i,w}|\leq\tau_{0}/2^{\ell}$.

Let $(q,\tau_{0})$ be any (query function, tolerance) pair that $A$ may make
in the course of its execution. We show that a $\pm\tau_{0}$-accurate estimate
$\widehat{P}_{q}$ of $P_{q}$ can be computed from the responses to the
$n2^{\ell}$ queries of $A^{\prime}$. This is easily seen to imply the lemma.

Since $A$ is $\ell$-local, the expected value $P_{q}$ is

$P_{q}=\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[q^{\prime}(\boldsymbol{y}_{i},\dots,\boldsymbol{y}_{i+\ell-1})]$

for some $q^{\prime}:\\{0,1\\}^{\ell}\to[-1,1]$ and some $i\in[n]$. Since

$P_{q}=\sum_{w\in\\{0,1\\}^{\ell}}p_{i,w}\cdot q^{\prime}(w),$

by setting $\widehat{P}_{q}$ to be

$P_{q}=\sum_{w\in\\{0,1\\}^{\ell}}\widehat{p}_{i,w}\cdot q^{\prime}(w),$

recalling that $|q^{\prime}(w)|\leq 1$ for all $w$, the triangle inequality
gives

$|\widehat{P}_{q}-P_{q}|=\left|\sum_{w\in\\{0,1\\}^{\ell}}(\widehat{p}_{i,w}-p_{i,w})\cdot
q^{\prime}(w)\right|\leq\max_{w}|q^{\prime}(w)|\cdot\sum_{w}|\widehat{p}_{i,w}-p_{i,w}|\leq\sum_{w}\tau_{0}/2^{\ell}\leq\tau_{0}$

as desired. ∎

##  3 Worst-case lower bounds

In this section we prove the following lower bound on local SQ algorithms for
the worst-case trace reconstruction problem:

######  Theorem 6 (Worst-case lower bound).

Fix any constant deletion rate $0<\delta<1$. For a suitable absolute constant
$c_{0}$, any $c_{0}n^{1/5}/(\log n)^{2/5}$-local SQ algorithm for worst-case
trace reconstruction must have tolerance $\tau_{0}<\exp(-\Omega(n^{1/5}/(\log
n)^{2/5})).$

Setup. Fix any $0<\delta<1$. For notational clarity let us write
$\ell:=c_{0}n^{1/5}/(\log n)^{2/5}$. Given an $n$-bit source string $x$, an
index $i\in[0:n-1]$, and an $\ell$-bit string $w$, we define the value

$p_{x,i,w}:=\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[(\boldsymbol{y}_{i},\dots,\boldsymbol{y}_{i+\ell-1})=w],$
(2)

so $p_{x,i,w}$ is the probability that a random trace of $x$ has $w$ as the
subword starting in position $i$. We refer to the vector
$(p_{x,i,w})_{i\in[0:n-1],w\in\\{0,1\\}^{\ell}}$ as the _$\ell$ -subword
signature_ of $x$.

We will prove the following:

######  Lemma 7.

For a suitable absolute constant $c_{0}$, there are distinct $n$-bit strings
$a\neq a^{\prime}\in\\{0,1\\}^{n}$ whose $\ell$-subword signatures are very
close to each other in $\ell_{\infty}$-distance: more precisely,

$\text{For all $i\in[0:n-1],w\in\\{0,1\\}^{\ell}$, we
have~{}}|p_{a,i,w}-p_{a^{\prime},i,w}|\leq\exp(-2c_{0}n^{1/5}/(\log
n)^{2/5}).$ (3)

To see why Lemma 7 implies Theorem 6, let $A$ be any $\ell$-local SQ algorithm
with tolerance $\exp(-c_{0}n^{1/5}/(\log n)^{2/5}).$ By Lemma 5, there is an
algorithm $A^{\prime}$ with the same behavior as $A$ which makes only subword
queries for subwords of length $\ell$, where each query of $A^{\prime}$ has
tolerance $\exp(-c_{0}n^{1/5}/(\log
n)^{2/5})/2^{\ell}>\exp(-2c_{0}n^{1/5}/(\log n)^{2/5})$. By Equation 3, a
query for the value of $p_{x,i,w}$ can be answered with the value
$q_{i,w}={\frac{p_{a,i,w}+p_{a^{\prime},i,w}}{2}}$ whether the source string
$x$ is $a$ or $a^{\prime}$. But this means that it is impossible for $A$ to be
an algorithm which successfully solves the worst-case trace reconstruction
problem.

In the rest of this section, we focus on establishing Lemma 7.

We require the following simple definition:

######  Definition 8.

Given $t>1$, we say that a string $x\in\\{0,1\\}^{n}$ is _$t$ -gappy_ if it is
of the form

$x=b_{0}0^{t-1}b_{1}0^{t-1}\cdots b_{n/t-1}0^{t-1}$

for some string $b_{0},b_{1},\dots,b_{n/t-1}\in\\{0,1\\}^{n/t}$.

Recall $\rho=1-\delta$. Fix

$t:={\frac{100\log(n)\ell}{\rho}}=\Theta(n^{1/5}(\log n)^{3/5}).$ (4)

The two strings $a,a^{\prime}$ whose existence is asserted by Lemma 7 will
both be $t$-gappy. (We note that the argument of Cheng et al. [CGL+23] also
used gappy strings.)

One reason that gappy strings are useful for us because they make it very easy
to handle almost all of the $\ell$-bit strings $w\in\\{0,1\\}^{\ell}$ that we
need to consider in order to establish Lemma 7. To see this, observe that any
string $w$ containing at least two ones is very unlikely to be a length-$\ell$
subword of a random trace $\boldsymbol{y}$: since the source string is
$t$-gappy, we expect consecutive ones in a random trace $\boldsymbol{y}$ to be
at least $\rho t\gg\ell$ positions apart from each other. More precisely, we
have the following lemma:

######  Lemma 9.

Let $x\in\\{0,1\\}^{n}$ be any $t$-gappy string, and let
$w\in\\{0,1\\}^{\ell}$ be any string with at least two ones. Then for any
$i\in[0:n-1]$ we have $p_{x,i,w}\leq 1/n^{49\ell}.$

###### Proof.

Fix $0\leq\alpha<\beta\leq\ell-1$ to be any two positions in $w$ such that
$w_{\alpha}=w_{\beta}=1$, and let
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)$. Observe that we have
$p_{x,i,w}\leq\operatorname{{\bf
Pr}}[\boldsymbol{y}_{i+\alpha}=\boldsymbol{y}_{i+\beta}=1]$.

Let
$\mathbf{R}=\\{\boldsymbol{r}_{0}<\boldsymbol{r}_{2}<\cdots<\boldsymbol{r}_{\boldsymbol{m}-1}\\}\subseteq[0:n-1]$
be the $\rho$-biased random subset of $[0:n-1]$ consisting of the indices that
are retained in $x$ to obtain $\boldsymbol{y}$. We may view the draw of
$\mathbf{R}$ as being carried out sequentially in independent stages
$0,1,\dots$, where in each stage $s$ the element $s$ is included in
$\mathbf{R}$ with probability $\rho$. Fix any outcome of stages $0,1,\dots$ up
until $r_{i+\alpha}$ has been included in $\mathbf{R}$. Even supposing that
$x_{r_{i+\alpha}}=1$ (so that $y_{i+\alpha}=1$), the probability that
$x_{\boldsymbol{r}_{i+\beta}}=1$ (which equals $\operatorname{{\bf
Pr}}[\boldsymbol{y}_{i+\beta}=1]$) is at most (writing $k$ for $\beta-\alpha$)

$\displaystyle\sum_{j\geq 1}\operatorname{{\bf Pr}}[\text{exactly $k$ of the
$jt$ indices in $r_{i+\alpha}+1,\dots,r_{i+\alpha}+jt$ are retained}]$ (5)
$\displaystyle=\sum_{j\geq 1}{jt\choose k}\rho^{k}\delta^{jt-k}$
$\displaystyle\leq\sum_{j\geq 1}(\rho jt)^{k}\cdot\delta^{jt/2}=(\rho
t)^{k}\sum_{j\geq 1}j^{k}\delta^{jt/2}$ $\displaystyle\leq(\rho
t)^{\ell}\sum_{j\geq 1}j^{\ell}(1-\rho)^{jt/2}$
$\displaystyle\leq(100\log(n)\ell)^{\ell}\sum_{j\geq
1}j^{\ell}e^{-50\log(n)\ell j}.$

When $j=1$ the first term of the sum $\sum_{j\geq 1}j^{\ell}e^{-50\log(n)\ell
j}$ is $e^{-50\log(n)\ell}$. The ratio of successive terms of the sum is

${\frac{(j+1)^{\ell}e^{-50\log(n)\ell(j+1)}}{j^{\ell}e^{-50\log(n)\ell
j}}}\leq 2^{\ell}e^{-50\log(n)\ell}=(2/n^{50})^{\ell}\ll 1/2.$

So the sum $\sum_{j\geq 1}j^{\ell}e^{-50\log(n)\ell j}$ is at most
$2e^{-50\log(n)\ell}=2/n^{50\ell}$, and since $100\log(n)\ell<n$ for $n$
sufficiently large, we get that $\eqref{eq:prob}\leq 1/n^{49\ell}.$ It follows
that $p_{x,i,w}\leq\operatorname{{\bf
Pr}}[\boldsymbol{y}_{i+\alpha}=\boldsymbol{y}_{i+\beta}=1]\leq 1/n^{49\ell}$
as claimed. ∎

Given Lemma 9 it remains to argue about the $\ell+1$ strings
$w\in\\{0,1\\}^{\ell}$ of Hamming weight 0 or 1. We handle the weight-1
strings by reducing their analysis to the analysis of _one-bit_ strings as
follows: fix any $\alpha\in[0:\ell-1]$ and let
$w=e_{\alpha}\in\\{0,1\\}^{\ell}$ be the string with a single 1 coordinate in
position $\alpha$. The following lemma, which we prove using Lemma 9, shows
that for any gappy source string $x$ the value of $p_{x,i,e_{\alpha}}$ is very
close to the expected value of a _single_ location in a random trace. (A
sharper bound could be obtained with a bit more work, but the bound given by
Lemma 10 is sufficient for our purposes.)

######  Lemma 10.

Let $x\in\\{0,1\\}^{n}$ be any $t$-gappy string, and let
$w=e_{\alpha}\in\\{0,1\\}^{\ell}$ be the string containing a single 1 in
coordinate $\alpha$. Then for any $i\in[0:n-1]$ we have

$\left|\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[\boldsymbol{y}_{i+\alpha}=1]-p_{x,i,e_{\alpha}}\right|\leq
2^{\ell-1}/n^{49\ell}.$

###### Proof.

We have

$\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[\boldsymbol{y}_{i+\alpha}=1]=\sum_{w\in\\{0,1\\}^{\ell}:w_{\alpha}=1}p_{x,i,w},\quad\text{so}$
$0\leq\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[\boldsymbol{y}_{i+\alpha}=1]-p_{x,i,e_{\alpha}}=\sum_{w\in\\{0,1\\}^{\ell}:w_{\alpha}=1,|w|\geq
2}p_{x,i,w}\leq(2^{\ell-1}-1)/n^{49\ell}$

where the inequality is Lemma 9. ∎

The one remaining $\ell$-bit string to consider is $w=0^{\ell}$. However, if
all $2^{\ell}-1$ other strings have been handled successfully then this string
is automatically handled as well:

######  Lemma 11.

Fix $a,a^{\prime}\in\\{0,1\\}^{n}$ and $i\in[0:n-1]$. Suppose that for all
$w\in\\{0,1\\}^{\ell}\setminus\\{0^{\ell}\\}$ we have
$|p_{a,i,w}-p_{a^{\prime},i,w}|\leq\kappa$. Then
$|p_{a,i,0^{\ell}}-p_{a^{\prime},i,0^{\ell}}|\leq(2^{\ell}-1)\kappa.$

###### Proof.

This is an immediate consequence of $\sum_{w\in\\{0,1\\}^{\ell}}p_{x,i,w}=1$,
which holds for every $x$ and $i$. ∎

Thus, it suffices to construct two $t$-gappy strings $a,a^{\prime}$ whose one-
bit statistics are very close:

######  Lemma 12.

For $x\in\\{0,1\\}^{n}$ and $i\in[0:n-1]$ define

$p_{x,i}:=\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[\boldsymbol{y}_{i}=1].$
(6)

Suppose that $a\neq a^{\prime}\in\\{0,1\\}^{n}$ are two $t$-gappy strings such
that for each $i\in[0:n-1]$ we have
$|p_{a,i}-p_{a^{\prime},i}|\leq\exp(-\Omega(n^{1/5}/(\log n)^{2/5})).$ Then
for all $i\in[0:n-1]$, $w\in\\{0,1\\}^{\ell}$ we have

$|p_{a,i,w}-p_{a^{\prime},i,w}|\leq 2^{\ell}\cdot\exp(-\Omega(n^{1/5}/(\log
n)^{2/5}))+4^{\ell}/n^{49\ell}\leq\exp(-2c_{0}n^{1/5}/(\log n)^{2/5}).$

###### Proof.

Lemma 9 gives $|p_{a,i,w}-p_{a^{\prime},i,w}|\leq 1/n^{49\ell}$ for $|w|\geq
2$. Lemma 10 and the assumption on $|p_{a,i}-p_{a^{\prime},i}|$ gives
$|p_{a,i,w}-p_{a^{\prime},i,w}|\leq\exp(-\Omega(n^{1/5}/(\log
n)^{2/5}))+2^{\ell}/n^{49\ell}$ for $|w|=1.$ Given these bounds, Lemma 11
gives $|p_{a,i,0^{\ell}}-p_{a^{\prime},i,0^{\ell}}|\leq
2^{\ell}\cdot\exp(-\Omega(n^{1/5}/(\log n)^{2/5}))+4^{\ell}/n^{49\ell}.$ ∎

###  3.1 Establishing closeness of one-bit statistics

Let us write $p_{x}=(p_{x,0},\dots,p_{x,n-1})$ to denote the $n$-dimensional
vector in $[0,1]^{n}$ whose coordinates are given by Equation 6. From the
results in the previous subsection it suffice to prove the following:

######  Lemma 13.

There are two distinct $t$-gappy strings $a,a^{\prime}\in\\{0,1\\}^{n}$ such
that for all $i\in[0:n-1]$ we have
$\|p_{a}-p_{a^{\prime}}\|_{\infty}\leq\exp(-\Omega(n^{1/5}/(\log n)^{2/5})).$

This is very similar to the main lower bound statement that was established in
the two works [DOS17, NP17] (independently of each other); those papers
considered “one-bit statistics” which correspond precisely to our $p_{x,i}$
quantities, and showed that there are two distinct strings
$x,x^{\prime}\in\\{0,1\\}^{n}$ (not restricted to be gappy) such that
$|p_{x,i}-p_{x^{\prime},i}|\leq\exp(-\Omega(n^{1/3}))$ for all $i\in[0:n-1]$.
In what follows we adapt their techniques to deal with $t$-gappy source
strings.

Following [DOS17], given a pair of source strings
$a,a^{\prime}\in\\{0,1\\}^{n}$ we define the corresponding _deletion-channel
polynomial_ (over $\mathbbm{C}$) to be

$P_{a,a^{\prime}}(z):=\sum_{i=0}^{n-1}(p_{a,i}-p_{a^{\prime},i})\cdot z^{i}.$
(7)

We have

$\|p_{a}-p_{a^{\prime}}\|_{\infty}\leq\|p_{a}-p_{a^{\prime}}\|_{1}\leq\sqrt{n}\max_{z\in\partial
D_{1}(0)}|P_{a,a^{\prime}}(z)|,$ (8)

where the second inequality is by Proposition 3.5 of [DOS17] (the proof is a
simple and standard computation about complex polynomials). Thus our goal is
to establish the existence of two distinct $t$-gappy strings $a\neq
a^{\prime}\in\\{0,1\\}^{n}$ for which $\max_{z\in\partial
D_{1}(0)}|P_{a,a^{\prime}}(z)|$ is small. To do this, we begin by observing
that since bit $j$ of a source string ends up in location $i$ of a trace with
probability ${j\choose i}\rho^{i+1}\delta^{j-i}$, we have

$p_{a,i}=\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(a)}[\boldsymbol{y}_{i}=1]=\sum_{j=0}^{n-1}{j\choose
i}\rho^{i+1}\delta^{j-i}a_{j},\quad\text{and hence}\quad
p_{a,i}-p_{a^{\prime},i}=\sum_{j=0}^{n-1}(a_{j}-a^{\prime}_{j}){j\choose
i}\rho^{i+1}\delta^{j-i}.$

Hence (following [DOS17, NP17]) we get

$\displaystyle P_{a,a^{\prime}}(z)$
$\displaystyle=\sum_{i=0}^{n-1}\left(\sum_{j=0}^{n-1}(a_{j}-a^{\prime}_{j}){j\choose
i}\rho^{i+1}\delta^{j-i}\right)z^{i}=\rho\sum_{j=0}^{n-1}(a_{j}-a^{\prime}_{j})\delta^{j}\sum_{i=0}^{n-1}{j\choose
i}\left({\frac{\rho z}{\delta}}\right)^{i}$
$\displaystyle=\rho\sum_{j=0}^{n-1}(a_{j}-a^{\prime}_{j})w^{j}\quad\text{(taking
$w=1-\rho+\rho z$)}$ (9)

where the last line used the binomial theorem and $\delta=1-\rho$. Now, let us
write the $t$-gappy strings $a,a^{\prime}$ as

$a:=b_{0}0^{t-1}b_{1}0^{t-1}\cdots b_{n/t}0^{t-1},\quad\quad\quad\quad
a^{\prime}:=b^{\prime}_{0}0^{t-1}b^{\prime}_{1}0^{t-1}\cdots
b^{\prime}_{n/t}0^{t-1}$ (10)

for some $b,b^{\prime}\in\\{0,1\\}^{n/t}$. From Equation 9 we get that

$P_{a,a^{\prime}}(z)=\rho\cdot\sum_{j=0}^{n/t-1}(b_{j}-b^{\prime}_{j})w^{jt}$
(11)

(the structure afforded by eq. 11 is another reason why $t$-gappy strings are
useful for us). Since $0<\rho=1-\delta<1$ is a constant, recalling eq. 8 our
goal is to establish the existence of a string $0^{n/t}\neq
v=(v_{0},\dots,v_{n/t-1})\in\\{-1,0,1\\}^{n/t}$ such that

$\max_{\theta\in(-\pi,\pi]}\left|\sum_{j=0}^{n/t-1}v_{j}\left((1-\rho+\rho
e^{i\theta})^{t}\right)^{j}\right|$ (12)

is small.

As described in Theorem 6.2 of [DOS17], a result of Borwein and Erdélyi [BE97]
(specifically, the first proof of Theorem 3.3 in the “special case” on p. 11
of [BE97]) establishes the following:

######  Theorem 14 ([BE97]).

There are universal constants $c_{1},c_{2},c_{3}>0$ such that the following
holds: For all $0<a\leq c_{1}$ there exists an integer $2\leq k\leq
c_{2}/a^{2}$ and a nonzero vector $u\in\\{-1,0,1\\}^{k+1}$ such that
$\max_{w\in D_{6a}(1)}|\sum_{j=0}^{k}u_{j}w^{j}|\leq\exp(-c_{3}/a)$.

Let $m=n^{1/5}/(\log n)^{2/5}=1/a$, so $a=1/m=(\log n)^{2/5}/n^{-1/5}.$
Recalling eq. 4, we have that $c_{2}/a^{2}=c_{2}m^{2}\ll n/(2t)$, so we get
that there exists a vector $0^{n/(2t)}\neq u\in\\{-1,0,1\\}^{n/(2t)}$ such
that

$\max_{w\in
D_{6/m}(1)}\left|\sum_{j=0}^{n/(2t)-1}u_{j}w^{j}\right|\leq\exp(-c_{3}m).$
(13)

Routine geometry shows that if $|\theta|\leq{\frac{1}{mt}}$ then
$|1-(1-\rho+\rho e^{i\theta})^{t}|\leq 6/m$, so we get that

$\max_{|\theta|\leq 1/(mt)}\left|\sum_{j=0}^{n/(2t)-1}u_{j}\left((1-\rho+\rho
e^{i\theta})^{t}\right)^{j}\right|\leq\exp(-c_{3}m).$ (14)

Now we can describe our final desired string $v\in\\{-1,0,1\\}^{n/t}$: it is
obtained by padding $u$ with a prefix of $n/(2t)$ many zeros. We thus have

$\eqref{eq:v}=\max_{\theta\in(-\pi,\pi]}\sum_{j=0}^{n/t-1}v_{j}\left((1-\rho+\rho
e^{i\theta})^{t}\right)^{j}=\max_{\theta\in(-\pi,\pi]}\left(\overbrace{(1-\rho+\rho
e^{i\theta})^{n/2}}^{A}\cdot\overbrace{\sum_{j=0}^{n/(2t)-1}u_{j}\left((1-\rho+\rho
e^{i\theta})^{t}\right)^{j}}^{B}\right).$ (15)

Since $|1-\rho+\rho e^{i\theta}|\leq 1$ for all $\theta\in(-\pi,\pi]$, we have
that $|A|$ is always at most 1 and $|B|$ is always at most $n/(2t)$. We bound
eq. 15 by considering two possible ranges for $|\theta|$. If $|\theta|\leq
1/(mt)$, then since $|A|\leq 1$, from eq. 14 we have that $\eqref{eq:AB}\leq
1\cdot|B|\leq\exp(-c_{3}m).$ On the other hand, if $|\theta|>1/(mt)$ then
since $|B|\leq n/(2t)$ and $\rho$ is a constant between 0 and 1, we get that
$|1-\rho+\rho e^{i\theta}|\leq 1-{\frac{c_{\rho}}{(mt)^{2}}}$, and hence

$\eqref{eq:AB}\leq{\frac{n}{2t}}\cdot|A|\leq{\frac{n}{2t}}\cdot\left(1-\frac{c_{\rho}}{(mt)^{2}}\right)^{n/2}\leq\exp(-c^{\prime}_{\rho}n/(mt)^{2})$

for two constants $c_{\rho},c^{\prime}_{\rho}>0$ that depend only on $\rho.$
Since $m=n^{1/5}/(\log n)^{2/5}$ and $n/(mt)^{2}=\Theta(n^{1/5}/(\log
n)^{2/5})$, for all $\theta\in(-\pi,\pi]$ we have that
$\eqref{eq:v}\leq\exp(-\Omega(n^{1/5}/(\log n)^{2/5}))$, so the proof of Lemma
13 and hence of Theorem 6 is complete.

##  4 Worst-case upper bounds

In this section we will give a local SQ algorithm for worst-case trace
reconstruction, proving Theorem 2.

######  Theorem 15 (Worst-case upper bound).

Fix any constant deletion rate $0<\delta<1$. There is a worst-case SQ trace
reconstruction algorithm that makes only $(O(n^{1/5}\log^{5}n))$-local queries
with tolerance $\tau=2^{-O(n^{1/5}\log^{5}n)}$.

Overview. As discussed in the introduction, [CGL+23] showed that the state-of-
the-art worst-case trace reconstruction algorithm of Chase [Cha21b] can be
interpreted as a $\tilde{O}(n^{1/5})$-mer based algorithm, and further
observed that the work [MS23] implicitly showed that for deletion rate
$\delta<1/2$, any $k$-mer based algorithm only relies on local statistics of
random traces. The same observation can also be inferred from the work
[CDL+21b]; more generally, that work implicitly showed that for _any_ deletion
rate $0<\delta<1$ (not just $\delta<1/2$), Chase’s algorithm can be
interpreted as a local SQ algorithm. We obtain Theorem 15 by making this
interpretation explicit, without going through the notion of $k$-mer
statistics.

In the case of $\delta<1/2$, the observation in [CDL+21b, MS23] is the
following. Chase’s algorithm is based on estimating (from below) a certain
univariate polynomial $Q_{x}(z_{0})$ at some point $z_{0}$ inside the shifted
complex disc $D:=\\{\frac{z-\delta}{1-\delta}:\lvert z\rvert\leq 1\\}$.
Moreover, the degree-$\ell$ coefficient of $Q_{x}$ can be estimated using
$\ell$-local statistics. When $\delta$ is bounded away from $1/2$, these works
observed that the magnitude of the degree-$\ell$ term of $Q_{x}$ decays
exponentially in $\ell$, and so the contribution from the high-degree terms is
negligible and can be truncated from the evaluation.

In the case of $\delta\geq 1/2$, a point in $D$ can have magnitude $1$ or
more, and so the high-degree terms in $Q_{x}$ need not decay in magnitude.
Instead of evaluating the polynomial on some point in $D$, [CDL+21b] applies a
result by Borwein, Erdélyi, and Kós [BEK99] (see Lemma 18 below) which shows
that there exists a value $t_{0}$ in the real interval
$[\delta,\frac{1}{4}+\frac{3}{4}\delta]$ such that $Q_{x}(t_{0})$ is almost as
large as $Q_{x}(z_{0})$, and as a result, we can estimate the truncation of
$Q_{x}(t_{0})$ instead.

We now proceed to a detailed proof of Theorem 15. Let $\ell:=2n^{1/5}$. Our
$(O(n^{1/5}\log^{5}n))$-local SQ algorithm in Theorem 15 is based on the
following two lemmas. (Throughout this section, it will be more convenient for
us to phrase various quantities in terms of the retention rate
$\rho=1-\delta$.) For a source string $x\in\\{0,1\\}^{n}$ and an $\ell$-bit
pattern $w\in\\{0,1\\}^{\ell}$, let $P_{x,w}(z,t)$ be the following bivariate
polynomial:

$P_{x,w}(z,t):=\sum_{0\leq i_{1}<\cdots<i_{\ell}\leq
n-1}\prod_{k=1}^{\ell}\mathbf{1}\left[x_{i_{k}}=w_{k}\right]z^{i_{1}}\cdot
t^{i_{\ell}-i_{1}-(\ell-1)}.$

######  Lemma 16.

For every deletion rate $\delta\in(0,1)$, there is a constant $C_{\rho}$ such
that the following holds. For every distinct pair of source strings
$x,x^{\prime}\in\\{0,1\\}^{n}$, there is a pattern $w\in\\{0,1\\}^{\ell}$, a
point $z_{0}\in\\{e^{i\theta}:\lvert\theta\rvert\leq
n^{-2/5}\\}\cup[1-\rho,1-\frac{3}{4}\rho]$, and a real value
$t_{0}\in[1-\rho,1-\frac{3}{4}\rho]$, such that

$\lvert
P_{x,w}(z_{0},t_{0})-P_{x^{\prime},w}(z_{0},t_{0})\rvert\geq\exp\bigl{(}-C_{\rho}n^{1/5}\log^{5}n\bigr{)}.$

######  Lemma 17.

For every deletion rate $\delta\in(0,1)$, there exists an SQ algorithm that
makes $C_{\rho}n^{1/5}\log^{5}n$-local queries with tolerance
$\exp(-C_{\rho}n^{1/5}\log^{5}n)$ such that for every $w\in\\{0,1\\}^{\ell}$,
$z\in\\{e^{i\theta}:\lvert\theta\rvert\leq
n^{-2/5}\\}\cup[1-\rho,1-\frac{3}{4}\rho]$, and
$t\in[1-\rho,1-\frac{3}{4}\rho]$ it outputs an estimate
$\widehat{P_{x,w}}(z,t)$ of $P_{x,w}(z,t)$ that is accurate to within $\pm
0.1\cdot\exp(-C_{\rho}n^{1/5}\log^{5}n)$.

#### Our $\ell$-local SQ algorithm (Proof of Theorem 15 assuming Lemmas 16 and
17).

Given an unknown source string $x\in\\{0,1\\}^{n}$, our reconstruction
algorithm enumerates every pair of distinct strings $x_{1}\neq
x_{2}\in\\{0,1\\}^{n}$. For each such pair, it considers the triple
$(w,z_{0},t_{0})$ for that pair whose existence is given by Lemma 16. (Hence
there are at most $2^{2n}$ many such triples $(w,z_{0},t_{0})$ considered in
total.) Then it uses the SQ algorithm in Lemma 17 to obtain an accurate
estimate $\widehat{P_{x,w}}(z_{0},t_{0})$ of $P_{x,w}(z_{0},t_{0})$ for each
$w$ within an additive factor of $\pm
0.1\cdot\exp(-C_{\rho}n^{1/5}\log^{5}n)$, and outputs the $x^{\prime}$ such
that $\widehat{P_{x,w}}(z_{0},t_{0})$ and $P_{x^{\prime},w}(z_{0},t_{0})$ are
$\pm 0.5\cdot\exp(-C_{\rho}n^{1/5}\log^{5}n)$-close to each other for every
$w,z_{0},t_{0}$. The correctness follows immediately from Lemma 16, because if
$x^{\prime}\neq x$, then by that lemma there is some $(w,z_{0},t_{0})$ such
that by the triangle inequality we have

$\displaystyle\lvert\widehat{P_{x,w}}(z_{0},t_{0})-P_{x^{\prime},w}(z_{0},t_{0})\rvert$
$\displaystyle\geq\lvert
P_{x,w}(z_{0},t_{0})-P_{x^{\prime},w}(z_{0},t_{0})\rvert-\lvert\widehat{P_{x,w}}(z_{0},t_{0})-P_{x,w}(z_{0},t_{0})\rvert$
$\displaystyle\geq 0.9\cdot\exp(-C_{\rho}n^{1/5}\log^{5}n).$

###  4.1 Proof of Lemma 16

In this subsection we prove Lemma 16. We first recall the following result
from [BEK99].

######  Lemma 18 (Theorem 5.1 in [BEK99]).

There are constants $c_{1},c_{2}>0$ such that for every analytic function $f$
on the open unit disc $\\{z:\lvert z\rvert<1\\}$ with $\lvert
f(z)\rvert<\frac{1}{1-\lvert z\rvert}$ and every $a\in(0,1]$, we have

$\lvert
f(0)\rvert^{\frac{c_{1}}{a}}\leq\exp(c_{2}/a)\sup_{t\in[1-a,1-\frac{3}{4}a]}\lvert
f(t)\rvert.$

Note that polynomials with coefficients bounded by $1$ are clearly analytic
and satisfy the condition that $\lvert f(z)\rvert<\frac{1}{1-\lvert z\rvert}$
on the open unit disc $\\{z:\lvert z\rvert<1\\}$.

We note that in the actual statement in [BEK99, Theorem 5.1], the interval
containing $t$ is $[1-a,1]$. However, a close inspection of the proof reveals
that the interval can be restricted to be $[1-a,1-\frac{3}{4}a]$.
Specifically, their Theorem 5.1 is based on their Corollary 5.3, which in turn
is based on their Corollary 5.2, where the interval is taken to be
$[1-a,1-a+\frac{1}{4}a]$. A self-contained proof using essentially the same
argument can also be found in [CDL+21b, Theorem 9].

We further note that the difference between $[1-a,1]$ and $[1-\frac{3}{4}a]$
is crucial in showing that the contribution of the high-degree terms of the
relevant polynomial (Equation 16) is negligible. Had $t$ been $1$, then
$\frac{t-(1-\rho)}{\rho}=1$ and there would have been no exponential decay in
the high-degree terms.

Lemma 16 follows from two cases below.

#### Case 1: $x_{i}\neq x^{\prime}_{i}$ for some $0\leq i\leq\ell-1$.

In this case, we consider the $\ell$-bit pattern $w:=x[0:\ell-1]$. Note that
$P_{x,w}(0,0)-P_{x^{\prime},w}(0,0)=\mathbf{1}\left[x[0:\ell-1]=w\right]-\mathbf{1}\left[x^{\prime}[0:\ell-1]=w\right]=1$.
We now apply Lemma 18 twice. The first application is to the polynomial
$Q_{1}(z_{1}):=P_{x,w}(z_{1},0)-P_{x^{\prime},w}(z_{1},0)$, which implies that
there exists some $z_{0}\in[1-\rho,1-\frac{3}{4}\rho]$ such that

$\lvert Q_{1}(z_{0})\rvert\geq e^{-c_{2}/\rho}\lvert
Q_{1}(0)\rvert^{c_{1}/\rho}=e^{-c_{2}/\rho}\lvert
P_{x,w}(0,0)-P_{x^{\prime},w}(0,0)\rvert^{c_{1}/\rho}=e^{-c_{2}/\rho}.$

We now apply Lemma 18 again to the polynomial

$Q_{2}(z_{2}):=\frac{P_{x,w}(z_{0},z_{2})-P_{x^{\prime},w}(z_{0},z_{2})}{\binom{n}{\ell}}.$

Note that all coefficients in $Q_{2}$ have magnitude at most $1$. This implies
the existence of some $t_{0}\in[1-\rho,1-\frac{3}{4}\rho]$ such that

$\displaystyle\lvert
P_{x,w}(z_{0},t_{0})-P_{x^{\prime},w}(z_{0},t_{0})\rvert=\binom{n}{\ell}\lvert
Q_{2}(t_{0})\rvert$ $\displaystyle\geq\binom{n}{\ell}e^{-c_{2}/\rho}\lvert
Q_{2}(0)\rvert^{c_{1}/\rho}=\binom{n}{\ell}e^{-c_{2}/\rho}\left({\frac{\lvert
Q_{1}(z_{0})\rvert}{{n\choose\ell}}}\right)^{c_{1}/\rho}$
$\displaystyle\geq\frac{e^{-\frac{c_{2}}{\rho}-\frac{c_{1}c_{2}}{\rho^{2}}}}{{n\choose\ell}^{\frac{c_{1}}{\rho}-1}}\geq
e^{-\Omega_{\rho}(\ell\log n)}=e^{-\Omega_{\rho}(n^{1/5}\log n)},$

where the last inequality used $\binom{n}{\ell}\geq(n/\ell)^{\ell}$, and the
last equality follows from our choice of $\ell=2n^{1/5}$. To conclude, there
exists some $(z_{0},t_{0})\in[1-\rho,1-\frac{3}{4}\rho]^{2}$ such that $\lvert
P_{x,w}(z_{0},t_{0})-P_{x^{\prime},w}(z_{0},t_{0})\rvert\geq\Omega_{\rho}({n\choose\ell}^{-c_{1}/\rho})$.

#### Case 2: $x_{i}=x^{\prime}_{i}$ for all $0\leq i\leq\ell-1$.

For this case, [Cha21b, Corollary 6.1] (with the interval $[1-2\rho,1]$
replaced with $[1-\rho,1-\frac{3}{4}\rho]$) can be restated, using Lemma 18 in
a similar fashion as Case 1, as follows:

######  Lemma 19 (Corollary 6.1 in [Cha21b], slightly rephrased and refined).

For every $\rho>0$, there exists a constant $C_{\rho}$ such that the following
holds. Let $\ell=2n^{1/5}$. For every distinct $x,x^{\prime}\in\\{0,1\\}^{n}$
where $x_{i}=x^{\prime}_{i}$ for every $0\leq i<\ell-1$, there exists a
pattern $w\in\\{0,1\\}^{\ell}$, a $z_{0}=e^{i\theta}$ for some
$\theta\in[-n^{-2/5},n^{-2/5}]$ and a $t_{0}\in[1-\rho,1-\frac{3}{4}\rho]$
such that

$\lvert\sum_{0\leq i_{1}<\cdots<i_{\ell}\leq
n-1}\Bigl{(}\prod_{k=1}^{\ell}\mathbf{1}\left[x_{i_{k}}=w_{k}\right]-\prod_{k=1}^{\ell}\mathbf{1}\left[x^{\prime}_{i_{k}}=w_{k}\right]\Bigr{)}z_{0}^{i_{1}}\cdot
t_{0}^{i_{\ell}-i_{1}-(\ell-1)}\rvert\geq\exp\bigl{(}-C_{\rho}n^{1/5}\log^{5}n\bigr{)}.$

Combining the two cases proves Lemma 16.

###  4.2 Proof of Lemma 17

We now prove Lemma 17. We first state the following identity relating two
multivariate polynomials, each of which is defined in terms of an arbitrary
$f:\\{0,1\\}^{\ell}\to\mathbbm{C}$. One of these involves the evaluation of
$f$ on the $\ell$-bit (not necessarily consecutive) substrings of the source
string $x$, and the other involves the expectation of $f$ evaluated on the
$\ell$-bit substrings of a random trace
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)$. This identity has now appeared
in several places such as [CDL+21b, Cha21b] (see [CDL+21b, Section 5.2] for a
proof).

######  Fact 20.

For every $f\colon\\{0,1\\}^{\ell}\to\mathbbm{C}$, $x\in\\{0,1\\}^{n}$,
$\rho\in[0,1]$, and $z\in\mathbbm{C}^{\ell}$,

$\displaystyle\rho^{\ell}\sum_{0\leq i_{1}<\cdots<i_{\ell}\leq
n-1}f(x_{i_{1}},\ldots,x_{i_{\ell}})\bigl{(}(1-\rho)+\rho
z_{1}\bigr{)}^{i_{1}}\prod_{k=2}^{\ell}\bigl{(}(1-\rho)+\rho
z_{k}\bigr{)}^{i_{k}-i_{k-1}-1}$ $\displaystyle=\sum_{0\leq
j_{1}<\cdots<j_{\ell}\leq n-1}\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{1-\rho}(x)}\bigl{[}f(\boldsymbol{y}_{j_{1}},\ldots,\boldsymbol{y}_{j_{\ell}})\bigr{]}z_{1}^{j_{1}}\prod_{k=2}^{\ell}z_{k}^{j_{k}-j_{k-1}-1}.$

Letting $f(u_{1},\ldots,u_{\ell})$ be the indicator function
$\mathbf{1}\left[u=w\right]$ for some pattern $w\in\\{0,1\\}^{\ell}$, then
performing a simple change of variable
$z_{i}\mapsto\frac{z_{i}-(1-\rho)}{\rho}$, and then identifying the variables
$z_{3},\ldots,z_{\ell}$ with the variable $z_{2}$, we obtain the following
corollary.

######  Corollary 21.

For every $\rho\in(0,1]$, $x\in\\{0,1\\}^{n}$, $w\in\\{0,1\\}^{\ell}$, and
$(z_{1},z_{2})\in\mathbbm{C}^{2}$,

$\displaystyle P_{x,w}(z_{1},z_{2})$ $\displaystyle=\rho^{-\ell}\sum_{0\leq
j_{1}<\cdots<j_{\ell}\leq n-1}\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{1-\rho}(x)}\Bigl{[}\prod_{k=1}^{\ell}\mathbf{1}\left[\boldsymbol{y}_{j_{k}}=w_{k}\right]\Bigr{]}\Bigl{(}\frac{z_{1}-(1-\rho)}{\rho}\Bigr{)}^{j_{1}}\Bigl{(}\frac{z_{2}-(1-\rho)}{\rho}\Bigr{)}^{j_{\ell}-j_{1}-(\ell-1)}.$
(16)

Let $Q(z_{1},z_{2})$ be the bivariate polynomial on the right hand side of
Equation 16. Observe that for every fixed $z_{1}$, viewing $Q(z_{1},z_{2})$ as
a univariate polynomial in $z_{2}$, its $z_{2}$-coefficient of degree $d$ (a
univariate polynomial in $z_{1}$) can be estimated using $d$-local SQs. We
will first prove that $Q$, as a univariate polynomial in the second variable
$z_{2}$, is close to its low-degree truncation $Q_{\leq d}$ (for a suitable
choice of $d$), defined by

$\displaystyle Q_{\leq
d}(z_{1},z_{2}):=\rho^{-\ell}\sum_{\begin{subarray}{c}0\leq
j_{1}<\cdots<j_{\ell}\leq n-1:\\\ j_{\ell}-j_{1}-(\ell-1)\leq
d\end{subarray}}\mathop{{\bf
E}\/}_{\boldsymbol{y}}\Bigl{[}\prod_{k=1}^{\ell}\mathbf{1}\left[\boldsymbol{y}_{j_{k}}=w_{k}\right]\Bigr{]}\Bigl{(}\frac{z_{1}-(1-\rho)}{\rho}\Bigr{)}^{j_{1}}\Bigl{(}\frac{z_{2}-(1-\rho)}{\rho}\Bigr{)}^{j_{\ell}-j_{1}-(\ell-1)},$
(17)

when both $z_{1},z_{2}$ belong to the domain in Lemma 16.

######  Claim 22.

Let $C^{\prime\prime}_{\rho}$ be a constant, and $d_{0}\geq
C^{\prime\prime}_{\rho}(\ell+n^{1/5})+2\log n$. For every
$z\in\\{e^{i\theta}:\lvert\theta\rvert\leq
n^{-2/5}\\}\cup[1-\rho,1-\frac{3}{4}\rho]$ and
$t\in[1-\rho,1-\frac{3}{4}\rho]$, we have $\lvert Q_{\leq
d_{0}}(z,t)-Q(z,t)\rvert\leq 4\cdot 2^{-d_{0}/2}$.

###### Proof.

It suffices to show that for every $d\geq d_{0}$, the homogeneous degree-$d$
(in the variable $t$) term of $Q$, that is,

$\displaystyle\rho^{-\ell}\sum_{\begin{subarray}{c}0\leq
j_{1}<\cdots<j_{\ell}\leq n-1\\\ 0\leq
j_{\ell}-j_{1}-(\ell-1)=d\end{subarray}}\mathop{{\bf
E}\/}\Bigl{[}\prod_{k=1}^{\ell}\mathbf{1}\left[\boldsymbol{y}_{j_{k}}=w_{k}\right]\Bigr{]}\Bigl{(}\frac{z-(1-\rho)}{\rho}\Bigr{)}^{j_{1}}\Bigl{(}\frac{t-(1-\rho)}{\rho}\Bigr{)}^{j_{\ell}-j_{1}-(\ell-1)},$
(18)

is bounded by $2^{-d/2}$, as then we have $\lvert Q(z,t)-Q_{\leq
d_{0}}(z,t)\rvert\leq\sum_{d>d_{0}}2^{-d/2}=4\cdot 2^{-d_{0}/2}$, as desired.

We now bound Equation 18 as follows. First, the expectation in each term of
the summation can be bounded by $1$. Second, writing $z$ as $e^{i\theta}$ for
some $\lvert\theta\rvert\leq n^{-2/5}$, and using $\lvert\cos\theta\rvert\geq
1-\theta^{2}/2$, we have

$\displaystyle\lvert z-(1-\rho)\rvert^{2}$
$\displaystyle=\bigl{(}\cos\theta-(1-\rho)\bigr{)}^{2}+\sin^{2}\theta=1-2(1-\rho)\cos\theta+(1-\rho)^{2}$
$\displaystyle=2(1-\rho)(1-\cos\theta)+\rho^{2}\leq(1-\rho)\theta^{2}+\rho^{2}.$

Using $\lvert\theta\rvert\leq n^{-2/5}$ and $j_{1}\leq n$, when
$z=e^{i\theta}$ for some $\lvert\theta\rvert\leq n^{-2/5}$ we have that

$\Big{\lvert}\frac{z-(1-\rho)}{\rho}\Big{\rvert}^{j_{1}}\leq\biggl{(}1+(1-\rho)\Bigl{(}\frac{\theta}{\rho}\Bigr{)}^{2}\biggr{)}^{j_{1}/2}\leq
e^{C^{\prime}_{\rho}n^{1/5}}$ (19)

for some constant $C^{\prime}_{\rho}$. And when
$z\in[1-\rho,1-{\frac{3}{4}}\rho]$ we have $0\leq\frac{z-(1-\rho)}{\rho}\leq
1/4$ and so Equation 19 is again satisfied (with room to spare). Similarly,
for $t\in[1-\rho,1-\frac{3}{4}\rho]$ we have $0\leq\frac{t-(1-\rho)}{\rho}\leq
1/4$, and so $\lvert\left(\frac{t-(1-\rho)}{\rho}\right)^{d}\rvert\leq
4^{-d}$.

Finally, the number of indices $0\leq j_{1}<\cdots<j_{\ell}\leq n-1$ with
$j_{\ell}-j_{1}-(\ell-1)=d$ is at most $n\cdot\binom{(\ell-2)+d}{\ell-2}\leq
n\cdot 2^{d+(\ell-2)}$. So the degree-$d$ term (18) can be bounded by

$\rho^{-\ell}\cdot n\cdot 2^{d+\ell-2}\cdot e^{C^{\prime}_{\rho}n^{1/5}}\cdot
4^{-d}\leq n\cdot(2/\rho)^{\ell}\cdot e^{C^{\prime}_{\rho}n^{1/5}}\cdot
2^{-d},$

which is at most $2^{-d/2}$ whenever $d\geq
C^{\prime\prime}_{\rho}(\ell+n^{1/5})+2\log n$, for some constant
$C^{\prime\prime}_{\rho}$. ∎

We now describe our local SQ algorithm to approximate the low-degree
polynomial $Q_{\leq d}(z,t)$, for any
$(z,t)\in\\{e^{i\theta}:\lvert\theta\rvert\leq
n^{-2/5}\\}\cup[1-\rho,1-\frac{3}{4}\rho]\times[1-\rho,1-\frac{3}{4}\rho]$.
Set $d_{0}:=C^{\prime\prime}_{\rho}n^{1/5}\log^{5}n\geq
C^{\prime\prime}_{\rho}(\ell+n^{1/5})+2\log n$. Our $d_{0}$-local algorithm
makes the following $d_{0}$-local queries:

$\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{1-\rho}(x)}\Bigl{[}\mathbf{1}\left[\boldsymbol{y}[j:j+d_{0}-1]=u\right]\Bigr{]}\text{
for every $u\in\\{0,1\\}^{d_{0}}$ and $j\in\\{0,\ldots,n-1\\}$}.$

Let $\widehat{p_{u,j}}$ be the estimate of $\operatorname{{\bf
E}}[\mathbf{1}\left[\boldsymbol{y}[j:j+d_{0}-1]=u\right]]$ that is received as
a response to the query. For every fixed tuple $0\leq
j_{1}<\cdots<j_{\ell}\leq n-1$ such that $j_{\ell}-j_{1}-(\ell-1)\leq d_{0}$,
using the identity

$\operatorname{{\bf
E}}\Bigl{[}\prod_{k=1}^{\ell}\mathbf{1}\left[\boldsymbol{y}_{j_{k}}=w_{k}\right]\Bigr{]}=\sum_{u\in\\{0,1\\}^{d_{0}}:\forall
k\in[\ell]:u_{j_{k}-j_{1}+1}=w_{k}}\operatorname{{\bf
E}}\Bigl{[}\mathbf{1}\left[\boldsymbol{y}[j_{1}:j_{1}+d_{0}-1]=u\right]\Bigr{]},$

which is a sum of $2^{d_{0}-\ell}$ terms, the algorithm computes the estimate
$\widehat{p_{u,j_{1},\ldots,j_{\ell}}}$ of $\operatorname{{\bf
E}}\left[\prod_{k=1}^{\ell}\mathbf{1}\left[\boldsymbol{y}_{j_{k}}=w_{k}\right]\right]$
(using the estimates $\widehat{p_{u,j_{1}}}$ of $\operatorname{{\bf
E}}[\mathbf{1}\left[\boldsymbol{y}[j_{1}:j_{1}+d_{0}-1]=u\right]]$) by

$\widehat{p_{w,j_{1},\ldots,j_{\ell}}}:=\sum_{u\in\\{0,1\\}^{d_{0}}:\forall
k\in[\ell]:u_{j_{k}-j_{1}+1}=w_{k}}\widehat{p_{u,j_{1}}},$

for each $w\in\\{0,1\\}^{\ell}$ and tuple of indices $0\leq
j_{1}<\cdots<j_{\ell}\leq n-1$ such that $j_{\ell}-j_{1}-(\ell-1)\leq d_{0}$.
If the tolerance for each query is $\tau_{0}$, then the error of each estimate
$\widehat{p_{w,j_{1},\ldots,j_{\ell}}}$ is $\pm 2^{d_{0}-\ell}\cdot\tau_{0}$.
Finally, the algorithm computes the estimate $\widehat{Q_{\leq d_{0}}}(z,t)$
of $Q_{\leq d_{0}}(z,t)$ using Equation 17, as

$\widehat{Q_{\leq d_{0}}}(z,t):=\rho^{-\ell}\sum_{\begin{subarray}{c}0\leq
j_{1}<\cdots<j_{\ell}\leq n-1:\\\ j_{\ell}-j_{1}-(\ell-1)\leq
d_{0}\end{subarray}}\widehat{p_{w,j_{1},\ldots,j_{\ell}}}\Bigl{(}\frac{z-(1-\rho)}{\rho}\Bigr{)}^{j_{1}}\Bigl{(}\frac{t-(1-\rho)}{\rho}\Bigr{)}^{j_{\ell}-j_{1}-(\ell-1)}.$

There are at most $n\cdot\binom{d_{0}+(\ell-1)}{\ell-1}\leq n\cdot
2^{d_{0}+(\ell-1)}$ such tuples. So the total error is $n\cdot
2^{d_{0}+(\ell-1)}\cdot 2^{d_{0}-\ell}\cdot\tau_{0}\leq n\cdot
2^{2d_{0}}\cdot\tau_{0}$.

By Claim 22, we have that for every $(z,t)$ in the domain specified in Lemma
17

$\displaystyle\lvert\widehat{Q_{\leq d_{0}}}(z,t)-P_{x,w}(z,t)\rvert$
$\displaystyle=\lvert\widehat{Q_{\leq d_{0}}}(z,t)-Q(z,t)\rvert$
$\displaystyle\leq\lvert\widehat{Q_{\leq d_{0}}}(z,t)-Q_{\leq
d_{0}}(z,t)\rvert+\lvert Q_{\leq d_{0}}(z,t)-Q(z,t)\rvert$ $\displaystyle\leq
n\cdot 2^{2d_{0}}\cdot\tau_{0}+4\cdot 2^{-d_{0}/2}$
$\displaystyle=2^{2C^{\prime\prime}_{\rho}n^{1/5}\log^{5}n}\tau_{0}+\exp(-C^{\prime\prime}_{\rho}n^{1/5}\log^{5}n).$

Setting the tolerance parameter $\tau_{0}$ to be
$\exp(-C_{\rho}n^{1/5}\log^{5}n)$ proves Lemma 17.

##  5 Average-case lower bounds

######  Theorem 23 (Average-case lower bound).

Fix any constant deletion rate $0<\delta<1$. Any $\ell$-local SQ algorithm for
average-case trace reconstruction must have tolerance $\tau_{0}\leq
O(\ell/\sqrt{n}).$

Let $x$ be an arbitrary fixed string in $\\{0,1\\}^{n}$ and let $x^{\prime}$
be the string obtained from $x$ by flipping the bit $x_{n/2}$ in the middle.
Let $q:\\{0,1\\}^{n}\rightarrow[-1,1]$ be any $\ell$-junta query (which is not
necessarily $\ell$-local), i.e., there are $0\leq i_{1}<\ldots<i_{\ell}<n$
such that $q(x)=q^{\prime}(x_{i_{1}},\ldots,x_{i_{\ell}})$ for some
$q^{\prime}:\\{0,1\\}^{\ell}\rightarrow[-1,1]$. We will prove the following
claim:

######  Claim 24.

Let $P_{q}:=\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)}[q(\boldsymbol{y})]$ and
$P_{q}^{\prime}:=\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x^{\prime})}[q(\boldsymbol{y})].$
Then $|P_{q}-P_{q}^{\prime}|\leq O(\ell/\sqrt{n})$.

###### Proof.

Let $\mathbf{R}$ be a $\rho$-biased random draw of a subset of $[0:n-1]$ with
$\mathbf{R}=\\{\boldsymbol{r}_{0},\boldsymbol{r}_{1},\ldots,\boldsymbol{r}_{\boldsymbol{m}-1}\\}$
for some $\boldsymbol{m}\leq n$. Given that the only difference between $x$
and $x^{\prime}$ is the middle bit, we have

$\big{|}P_{q}-P_{q}^{\prime}\big{|}\leq 2\cdot\operatorname{{\bf
Pr}}_{\mathbf{R}}\left[\text{$\boldsymbol{r}_{i_{j}}=n/2$ for some
$j\in[\ell]$}\right]\leq 2\sum_{j\in[\ell]}\operatorname{{\bf
Pr}}_{\mathbf{R}}\left[\text{$\boldsymbol{r}_{i_{j}}=n/2$}\right].$

Since $\delta\in(0,1)$ is a constant, $\operatorname{{\bf
Pr}}_{\mathbf{R}}[\boldsymbol{r}_{i}=n/2]\leq O(1/\sqrt{n})$ for any $i$, from
which the claim follows. ∎

We now prove Theorem 23:

###### Proof.

(of Theorem 23) Indeed we will show that any SQ algorithm for average-case
trace reconstruction that uses $\ell$-junta queries with tolerance $\tau$ must
satisfy $\tau\leq O(\ell/\sqrt{n})$. To see this, consider any SQ algorithm
for trace reconstruction that uses $\ell$-junta queries with tolerance $\tau$
that is larger than the $O(\ell/\sqrt{n})$ in Claim 24. It follows from Claim
24 that, for any string $x\in\\{0,1\\}^{n}$, such an algorithm cannot
distinguish between $x$ and $x^{\prime}$. As a result, such an algorithm fails
to reconstruct $\boldsymbol{x}\sim\\{0,1\\}^{n}$ with probability at least
$1/2$. ∎

##  6 Average-case upper bounds

######  Theorem 25 (Average-case upper bound).

Fix any constant deletion rate $0<\delta<1$. There is an SQ algorithm for
average-case trace reconstruction that uses $\ell=O(\log n)$-local queries
with tolerance $\tau=1/\mathrm{poly}(n)$.

We will prove Theorem 25 by showing that the algorithm in [CDL+22] can be
simulated with local SQ queries. To do so, we will need to recall the smoothed
analysis model.

######  Definition 26.

Let $x^{\mathsf{worst}}$ be an unknown and arbitrary string in $\\{0,1\\}^{n}$
and $0<\sigma<1$ be a “smoothening parameter.” Let $\boldsymbol{x}$ be
generated by flipping every bit of $x^{\mathsf{worst}}$ independently with
probability $\sigma$.

For parameters $\eta,\tau>0$, a _$(T,\eta,\tau)$ -trace reconstruction
algorithm in the smoothed analysis model (with smoothening parameter
$\sigma$)_ has the following guarantee: With probability at least $1-\eta$
(over the random generation of $\boldsymbol{x}$ from $x^{\mathsf{worst}}$), it
is the case that the algorithm, given access to independent traces drawn from
$\mathbf{{Del}}_{\delta}(\boldsymbol{x})$, outputs the string $\boldsymbol{x}$
with probability at least $1-\tau$ (over the random traces drawn from
$\mathbf{{Del}}_{\delta}(\boldsymbol{x})$). The time complexity as well as the
number of traces is bounded by $T$.

Observe that the average case trace reconstruction setting corresponds to the
smoothed analysis setting with $\sigma=1/2$ and $x^{\mathsf{worst}}$ set to
the all zeros string (though any fixed choice of $x^{\mathsf{worst}}$ works
equally well).

[CDL+22] gave a polynomial-time algorithm for trace reconstruction in the
smoothed analysis setting. Taking $\sigma=1/2$, the main result of [CDL+22]
gives the following:

######  Theorem 27.

(Theorem 1 in [CDL+22]) There is an algorithm for trace reconstruction which
for any $\eta,\tau$ and $\delta>0$, has the following guarantee: With
probability $1-\eta$ over $\boldsymbol{x}$ drawn uniformly at random from
$\\{0,1\\}^{n}$, it is the case that the algorithm, given access to
independent traces drawn from $\mathbf{{Del}}_{\delta}(\boldsymbol{x})$,
outputs the string $\boldsymbol{x}$ with probability at least $1-\tau$ (over
the random traces drawn from $\mathbf{{Del}}_{\delta}(\boldsymbol{x})$). Its
running time and sample complexity are upper bounded by

$T=\bigg{(}\frac{n}{\eta}\bigg{)}^{O\big{(}\frac{1}{(1-\delta)}\cdot\log\big{(}\frac{2}{(1-\delta)}\big{)}\big{)}}.$

We begin with a short description of the algorithm in [CDL+22] (page 27 of the
Arxiv version of [CDL+22]), giving only the level of detail necessary for the
current paper. We set the following parameters:

$\displaystyle k$ $\displaystyle=$ $\displaystyle
O(\log(n/\eta)),\quad\kappa=\bigg{(}\frac{1}{n}\cdot\bigg{(}\frac{1-\delta}{2}\bigg{)}^{k}\bigg{)}^{O(1/(1-\delta))},\quad\quad\theta=(1-\delta)^{2}/2,\quad\quad$
$\displaystyle d$ $\displaystyle=$ $\displaystyle\frac{C}{\theta}\bigg{(}\ln
n+k\ln\frac{C}{\theta}\bigg{)},\quad\quad\Delta=\frac{\kappa}{2d^{2}\cdot
n\cdot\binom{d+k-2}{k-2}}.$ (20)

Set $L$ to be the largest integer such that
$\delta+L\cdot\delta\leq(1+\delta)/2$.

Given two strings $x\in\\{0,1\\}^{n}$ and $w\in\\{0,1\\}^{k}$, [CDL+22] define
a univariate polynomial $\mathsf{SW}_{x,w}(\cdot)$. The precise formal
definition of this polynomial is not important for us; rather, the following
relation (Equation 6 in the Arxiv version of [CDL+22]) is sufficient for our
purposes:

$~{}\mathop{{\bf
E}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)}[\\#(w,\boldsymbol{y})]=(1-\delta^{\prime})^{k}\cdot\mathsf{SW}_{x,w}(\delta^{\prime}),$
(21)

where $\\#(w,\boldsymbol{y})$ is the number of times $w$ appears a subword of
$\boldsymbol{y}$. We remark to the reader that $\\#(w,\boldsymbol{y})$ is a
sum of $k$-local query functions (we will elaborate on this shortly). The
algorithm in [CDL+22] proceeds as follows:

  1. 1.

Define set
$S:=\\{\delta,\delta+\Delta,\delta+2\Delta,\ldots,\delta+L\Delta\\}$.

  2. 2.

For every $w\in\\{0,1\\}^{k}$ and $\delta^{\prime}\in S$, the algorithm
computes $\pm\kappa$-accurate estimates of
$\mathsf{SW}_{x,w}(\delta^{\prime})$, using Equation 21.

  3. 3.

With these estimates of $\mathsf{SW}_{x,w}(\delta^{\prime})$ (for
$\delta^{\prime}\in S$ and $w\in\\{0,1\\}^{k}$), the algorithm runs a linear
program followed by a greedy algorithm to reconstruct the original string.

In particular, excluding the part of Step (2) in which the estimates of
$\mathsf{SW}_{x,w}(\delta^{\prime})$ are computed, the rest of the
reconstruction algorithm is deterministic and does not use the traces. Note
that the reason why the [CDL+22] algorithm does not immediately translate to a
local SQ algorithm for us is the following: in our model the permissible
statistical queries are with respect to
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta}(x)$, whereas the [CDL+22]
algorithm, as sketched above, uses estimates of probabilities corresponding to
statistical queries over
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)$ for various values of
$\delta^{\prime}>\delta.$

Thus, to obtain a local SQ algorithm, it suffices to show that the values
$\\{\mathsf{SW}_{x,w}(\delta^{\prime})\\}_{\delta^{\prime}\in S,\
w\in\\{0,1\\}^{k}}$ can be estimated using local SQ queries corresponding to
$\mathbf{{Del}}_{\delta}(x).$ More precisely, we have the following claim
whose proof is immediate from the description of the above algorithm and (21).

######  Claim 28.

For any $\delta^{\prime}\in S$, to compute
$\mathsf{SW}_{x,w}(\delta^{\prime})$ to error $\kappa$, it is sufficient to
estimate the value of $\operatorname{{\bf
E}}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)}[\\#(w,\boldsymbol{y})]$
up to error $\tau^{\prime}$, where

$~{}\tau^{\prime}:=\bigg{(}\frac{1}{n}\bigg{(}\frac{1-\delta}{2}\bigg{)}^{k}\bigg{)}^{O(1/(1-\delta))}.$
(22)

###### Proof.

We need to compute $\mathsf{SW}_{x,w}(\delta^{\prime})$ for
$\delta^{\prime}\in S$ to error $\kappa$. By (21), it suffices to compute
$\mathbf{E}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)}[\\#(w,\boldsymbol{y})]$
to error $\kappa\cdot(1-\delta^{\prime})^{k}$; noting that
$\delta^{\prime}\leq(1+\delta)/2$, the claim follows. ∎

The main technical lemma of this section is the following.

######  Lemma 29.

For the parameters defined as above, the following holds: Given the values of
all subword queries of length $\ell$ with tolerance $\tau^{\prime}/2$ (with
$\tau^{\prime}$ defined in (22)) corresponding to
$\mathbf{{Del}}_{\delta}(x)$, we can compute
$\mathsf{SW}_{x,w}(\delta^{\prime})$ for all $\delta^{\prime}\in S$ and
$w\in\\{0,1\\}^{k}$ to within error $\pm\kappa$. Here $\ell$ is defined to be

$\ell=\Theta\bigg{(}\frac{k}{1-\delta}\cdot\ln\bigg{(}\frac{2}{1-\delta}\bigg{)}+\frac{\ln
n}{(1-\delta)}\bigg{)}.$

Before proving this lemma, we observe that Theorem 25 follows immediately from
the lemma:

###### Proof.

(of Theorem 25) For any constant $0<\delta<1$ and $\eta=n^{-\Theta(1)}$, by
our choice of parameters we have $k=O(\log n)$ (see (20)). With this choice,
$\ell=O(\log n)$ and $\tau^{\prime}=n^{-\Theta(1)}$. By Lemma 29, using the
values of all subword queries of length $\ell$ (with tolerance
$\tau^{\prime}/2$), we can compute $\mathsf{SW}_{x,w}(\delta^{\prime})$ for
all $\delta^{\prime}\in S$ and $w\in\\{0,1\\}^{k}$ to within error
$\pm\kappa$. By the guarantee of the algorithm in [CDL+22], this suffices to
recover $x$. Thus, we get Theorem 25. ∎

###  6.1 Proof of Lemma 29

We start with the following observation.

######  Fact 30.

For $\delta^{\prime}\geq\delta$, let
$0\leq\beta_{r}=(1-\delta^{\prime})/(1-\delta)\leq 1$. Then
$\mathbf{{Del}}_{\delta^{\prime}}(x)=\mathbf{{Del}}_{\beta_{r}}(\mathbf{{Del}}_{\delta}(x))$.
In other words, we can simulate traces from the deletion channel
$\mathbf{{Del}}_{\delta^{\prime}}(\cdot)$ by first getting a trace from
$\mathbf{{Del}}_{\delta}(\cdot)$ and then passing it through the deletion
channel $\mathbf{{Del}}_{\beta_{r}}$.

As stated earlier, we will assume that our original string $x$ is padded with
infinitely many $0$-symbols to its right. This means that for any $i$, the
$i^{th}$ position of the trace is well-defined. We now consider the process of
getting a trace $\boldsymbol{y}$ from $\mathbf{{Del}}_{\delta^{\prime}}(x)$
given a trace $\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x)$. We will do this
by thinking of $\mathbf{{Del}}_{\beta_{r}}(\cdot)$ as a “selector process”. We
start with the following definition.

######  Definition 31.

For a parameter $p\in(0,1)$ and integers $k>0$ and $\ell\geq 0$, we define the
distribution $\mathsf{Hypernb}(p,k,\ell)$ as follows: Define an infinite
random string $\boldsymbol{w}=(\boldsymbol{w}_{0},\dots)$ in
$\\{0,1\\}^{\ast}$ where each bit is independently $0$ with probability $p$
and $1$ with probability $(1-p)$. Let $\mathbf{i}_{s}$ be the location of the
$s^{th}$ one in $\boldsymbol{w}$. Then a sample from
$\mathsf{Hypernb}(p,k,\ell)$ is given by
$(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell-1})$.

Finally, we say that an outcome from $\mathsf{Hypernb}(p,k,\ell)$ is _$t$
-bounded_ if $|\mathbf{i}_{k+\ell-1}-\mathbf{i}_{k}|\leq t$.

We note that for any fixed $s$, the process generating $\mathbf{i}_{s}$ is
memoryless, in the sense that for any fixed $r$ and $s$ (with $r\geq s$), the
random variable $\mathbf{i}_{r}-\mathbf{i}_{s}$ is distributed as a negative
binomial random variable.

With the above definition, we can now state the following claim:

######  Claim 32.

Fix $\delta^{\prime}\geq\delta$, $k\geq 1$, and $\ell\geq 0$. Let
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)$ and
$\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x)$. For
$\beta_{r}=(1-\delta^{\prime})/(1-\delta)$, let
$(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell-1})\sim\mathsf{Hypernb}(\beta_{r},k,\ell)$.
Then the distribution of
$(\boldsymbol{y}_{k},\ldots,\boldsymbol{y}_{k+\ell-1})$ is identical to the
distribution of
$(\boldsymbol{z}_{\mathbf{i}_{k}},\ldots,\boldsymbol{z}_{\mathbf{i}_{k+\ell-1}})$.

###### Proof.

The proof is essentially obvious from 30 and Definition 31. In particular,
from 30, given $\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x)$, to get
$\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)$, we need to simulate
the deletion channel $\mathbf{{Del}}_{\beta_{r}}$ on the string
$\boldsymbol{z}$. By definition of the deletion channel
$\mathbf{{Del}}_{\beta_{r}}$, the location of the positions
$(k,\ldots,k+\ell-1)$ is given by
$(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell-1})$ sampled from
$\mathsf{Hypernb}(p,k,\ell)$. This finishes the proof. ∎

We next need a lower bound on the probability that
$\mathsf{Hypernb}(p,k,\ell)$ is bounded. To obtain this, we first state a tail
bound on negative binomial random variables:

######  Claim 33 ([Bro11]).

Let $\mathsf{Negbin}(m,p)$ be a negative binomially distributed random
variable with parameters $m$ and $p$, i.e. it is the number of trials needed
to get $m$ heads from independent coin tosses with heads probability $p$. Then
$\mathbf{E}[\mathsf{Negbin}(m,p)]=m/p$ and furthermore, for any $t>1$,

$\operatorname{{\bf
Pr}}\bigl{[}\mathsf{Negbin}(m,p)>tm/p\bigr{]}\leq\exp\bigg{(}-\frac{tm(1-1/t)^{2}}{2}\bigg{)}.$

From this we can obtain the following claim which lower bounds the probability
that $\mathsf{Hypernb}(\beta_{r},k,\ell)$ is $s$-bounded.

######  Claim 34.

For any $k$, an outcome
$(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell-1})\sim\mathsf{Hypernb}(\beta_{r},k,\ell)$
is $s$-bounded with probability at least $1-\xi$ for $s=t(\ell-1)/\beta_{r}$,
where $\xi=\exp(-t(\ell-1)/8)$ for $t\geq 2$.

###### Proof.

The gap $\mathbf{i}_{k+\ell-1}-\mathbf{i}_{k}$ is a negative binomial random
variable which is distributed as $\mathsf{Negbin}(\ell-1,\beta_{r})$. Thus, by
Claim 33, it follows that

$\operatorname{{\bf
Pr}}\Bigl{[}\mathbf{i}_{k+\ell-1}-\mathbf{i}_{k}>\frac{t(\ell-1)}{\beta_{r}}\Bigr{]}\leq\exp\bigg{(}\frac{-t(\ell-1)(1-1/t)^{2}}{2}\bigg{)}.$

For $t\geq 2$, we can simplify the upper bound as

$\operatorname{{\bf
Pr}}\Bigl{[}\mathbf{i}_{k+\ell-1}-\mathbf{i}_{k}>\frac{t(\ell-1)}{\beta_{r}}\Bigr{]}\leq\exp\bigg{(}\frac{-t(\ell-1)}{8}\bigg{)}.$

Defining $\xi$ as $\exp(\frac{-t(\ell-1)}{8})$, we get the claim. ∎

We now state the following technical claim.

######  Claim 35.

Given the value of all $\ell$-local subword queries for deletion channel
$\mathbf{{Del}}_{\delta}(x)$ with tolerance $\eta$, we can compute the value
of all $\ell^{\prime}$-local subword queries for
$\mathbf{{Del}}_{\delta^{\prime}}(x)$ with tolerance $\tau^{\prime}$ where

$\eta=\tau^{\prime}/2;\quad\ell=C\cdot\bigg{(}\frac{\ell^{\prime}}{1-\delta^{\prime}}\cdot\ln\bigg{(}\frac{2}{1-\delta}\bigg{)}+\frac{\ln
n}{(1-\delta^{\prime})}\bigg{)},$

for a suitably large constant $C$.

###### Proof.

Fix any $w\in\\{0,1\\}^{\ell^{\prime}}$ and consider the quantity

$p^{\prime}_{x,k,w}:=\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)}[(\boldsymbol{y}_{k},\ldots,\boldsymbol{y}_{k+\ell^{\prime}-1})=w].$

Then, by Claim 32, it follows that

$~{}p^{\prime}_{x,k,w}:=\mathop{{\bf
Pr}\/}_{\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x),(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell^{\prime}-1})\sim\mathsf{Hypernb}(\beta_{r},k,\ell^{\prime})}[\boldsymbol{z}_{\mathbf{i}_{1}},\ldots,\boldsymbol{z}_{\mathbf{i}_{k+\ell^{\prime}-1}}=w],$
(23)

where $\beta_{r}=(1-\delta^{\prime})/(1-\delta)$. Define the parameter

$t=C\cdot\bigg{(}\frac{1}{1-\delta}\cdot\ln\bigg{(}\frac{2}{1-\delta}\bigg{)}+\frac{\ln
n}{\ell^{\prime}(1-\delta)}\bigg{)},$

where the constant $C$ is set so that

$\exp\bigg{(}\frac{t(\ell^{\prime}-1)}{8}\bigg{)}=\frac{\tau^{\prime}}{2}.$

As $\ell=t(\ell^{\prime}-1)/\beta_{r}$, it follows from Claim 34 that

$\operatorname{{\bf
Pr}}[\mathbf{i}_{\ell^{\prime}+k-1}-\mathbf{i}_{\ell^{\prime}}>\ell]\leq\exp\bigg{(}\frac{t(\ell^{\prime}-1)}{8}\bigg{)}=\frac{\tau^{\prime}}{2}.$
(24)

Now, define $\mathcal{E}$ as the event (over the samples
$(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell^{\prime}-1})$) that
$|\mathbf{i}_{k+\ell^{\prime}-1}-\mathbf{i}_{k}|\leq\ell$. We now re-express

$\displaystyle p^{\prime}_{x,k,w}$ $\displaystyle=$ $\displaystyle\mathop{{\bf
Pr}\/}_{\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x),(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell^{\prime}-1})}\bigl{[}\boldsymbol{z}_{\mathbf{i}_{1}},\ldots,\boldsymbol{z}_{\mathbf{i}_{k+\ell^{\prime}-1}}=w\
\wedge\mathcal{E}\bigr{]}$ $\displaystyle+$ $\displaystyle\mathop{{\bf
Pr}\/}_{\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x),(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell^{\prime}-1})}\bigl{[}\boldsymbol{z}_{\mathbf{i}_{1}},\ldots,\boldsymbol{z}_{\mathbf{i}_{k+\ell^{\prime}-1}}=w\
\wedge\overline{\mathcal{E}}\bigr{]}.$

From the bound (24), the second term is at most $\tau^{\prime}/2$ in magnitude
and thus,

$\Bigl{|}p^{\prime}_{x,k,w}-\mathop{{\bf
Pr}\/}_{\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x),(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell^{\prime}-1})}\bigl{[}\boldsymbol{z}_{\mathbf{i}_{1}},\ldots,\boldsymbol{z}_{\mathbf{i}_{k+\ell^{\prime}-1}}=w\
\wedge\mathcal{E}\bigr{]}\Bigr{|}\leq\tau^{\prime}/2.$

Furthermore, for any particular outcome of
$(\mathbf{i}_{k},\ldots,\mathbf{i}_{k+\ell^{\prime}-1})$ for which event
$\mathcal{E}$ happens, the quantity

$\mathop{{\bf
Pr}\/}_{\boldsymbol{z}\sim\mathbf{{Del}}_{\delta}(x)}[\boldsymbol{z}_{\mathbf{i}_{1}},\ldots,\boldsymbol{z}_{\mathbf{i}_{k+\ell^{\prime}-1}}=w],$

is a $\ell$-local subword query. Since we have the value of all $\ell$-local
subword queries up to error $\tau^{\prime}/2$, it follows that we can compute
$p^{\prime}_{x,k,w}$ to error $\tau^{\prime}$. ∎

###### Proof.

(of Lemma 29) By Claim 32, to compute $\mathsf{SW}_{x,w}(\delta^{\prime})$ to
error $\pm\kappa$, it suffices to compute
$\mathbf{E}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)}[\\#(w,\boldsymbol{y})]$
for every $w\in\\{0,1\\}^{\ell^{\prime}}$ up to error $\pm\tau^{\prime}$ where
$\tau^{\prime}$ is defined in (22). Now, by Claim 35, for any given
$\delta^{\prime}\geq\delta$, to compute
$\mathbf{E}_{\boldsymbol{y}\sim\mathbf{{Del}}_{\delta^{\prime}}(x)}[\\#(w,\boldsymbol{y})]$
to error $\tau$, it suffices to have the value of all $\ell$-local subword
queries to error $\tau^{\prime}/2$ where

$\ell=C\cdot\bigg{(}\frac{\ell^{\prime}}{1-\delta^{\prime}}\cdot\ln\bigg{(}\frac{2}{1-\delta}\bigg{)}+\frac{\ln
n}{(1-\delta^{\prime})}\bigg{)}.$

Since $\delta^{\prime}\leq(1+\delta)/2$, it follows that

$\ell\leq
C\cdot\bigg{(}\frac{2\ell^{\prime}}{1-\delta}\cdot\ln\bigg{(}\frac{2}{1-\delta}\bigg{)}+\frac{2\ln
n}{(1-\delta)}\bigg{)}.$

Thus, if we have the value of all $k$-local subword queries to error
$\tau^{\prime}/2$, where $k$ is set to

$k=\Theta\bigg{(}\frac{\ell^{\prime}}{1-\delta}\cdot\ln\bigg{(}\frac{2}{1-\delta}\bigg{)}+\frac{\ln
n}{(1-\delta)}\bigg{)},$

we can recover $x$. This finishes the proof. ∎

## References

  * [BCF+19] Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, and Sandip Sinha.  Beyond trace reconstruction: Population recovery from the deletion channel.  In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 745–768. IEEE Computer Society, 2019.
  * [BE97] Peter Borwein and Tamás Erdélyi.  Littlewood-type polynomials on subarcs of the unit circle.  Indiana University Mathematics Journal, 46(4):1323–1346, 1997.
  * [BEK99] Peter Borwein, Tamás Erdélyi, and Géza Kós.  Littlewood-type problems on $[0,1]$.  Proc. London Math. Soc. (3), 79(1):22–46, 1999.
  * [BKKM04] Tuǧkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor.  Reconstructing strings from random traces.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pages 910–918, 2004.
  * [BLS20] Joshua Brakensiek, Ray Li, and Bruce Spang.  Coded trace reconstruction in a constant number of traces.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 482–493, 2020.
  * [BR23] Tatiana Brailovskaya and Miklós Z. Rácz.  Tree trace reconstruction using subtraces.  J. Appl. Probab., 60(2):629–641, 2023.
  * [Bro11] Daniel G. Brown.  How I wasted too long finding a concentration inequality for sums of geometric variables.  Available at https://uwspace.uwaterloo.ca/bitstream/handle/10012/17210/negbin.pdf?sequence=1, 2011\.
  * [CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.  Approximate trace reconstruction via median string (in average-case).  In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 213 of LIPIcs, pages 11:1–11:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [CDL+21a] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the low deletion rate regime.  In 12th Innovations in Theoretical Computer Science Conference, volume 185, pages 20:1–20:20, 2021.
  * [CDL+21b] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the smoothed complexity model.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 54–73, 2021.
  * [CDL+22] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Near-optimal average-case approximate trace reconstruction from few traces.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 779–821, 2022.
  * [CGL+23] Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, and Minshen Zhu.  On k-mer-based and maximum likelihood estimation algorithms for trace reconstruction.  CoRR, abs/2308.14993, 2023.
  * [CGMR20] Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and João Ribeiro.  Coded trace reconstruction.  IEEE Trans. Inform. Theory, 66(10):6084–6103, 2020.
  * [Cha21a] Zachary Chase.  New lower bounds for trace reconstruction.  Ann. Inst. H. Poincaré Probab. Statist., 57(2):627–643, 2021\.
  * [Cha21b] Zachary Chase.  Separating words and trace reconstruction.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 21–31. ACM, 2021\.
  * [CP21] Z. Chase and Y. Peres.  Approximate trace reconstruction of random strings from a constant number of traces.  Available at https://arxiv.org/abs/2107.06454, 2021.
  * [DOS17] Anindya De, Ryan O’Donnell, and Rocco A. Servedio.  Optimal mean-based algorithms for trace reconstruction.  In Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), pages 1047–1056, 2017.
  * [DRR19] Sami Davies, Miklós Z. Rácz, and Cyrus Rashtchian.  Reconstructing trees from traces.  In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 961–978. PMLR, 2019\.
  * [DRRS21] Sami Davies, Miklos Z. Rácz, Cyrus Rashtchian, and Benjamin G. Schiffer.  Approximate trace reconstruction: Algorithms.  In IEEE International Symposium on Information Theory, 2021.
  * [GSZ21] Elena Grigorescu, Madhu Sudan, and Minshen Zhu.  Limitations of mean-based algorithms for trace reconstruction at small distance.  In IEEE International Symposium on Information Theory, 2021.
  * [HHP18] Lisa Hartung, Nina Holden, and Yuval Peres.  Trace reconstruction with varying deletion probabilities.  In Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018, New Orleans, LA, USA, January 8-9, 2018., pages 54–61, 2018.
  * [HL20] Nina Holden and Russell Lyons.  Lower bounds for trace reconstruction.  Ann. Appl. Probab., 30(2):503–525, 2020.
  * [HMPW08] Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder.  Trace reconstruction with constant deletion probability and related results.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pages 389–398, 2008.
  * [HPP18] Nina Holden, Robin Pemantle, and Yuval Peres.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1799–1840. PMLR, 2018.
  * [HPPZ19] Nina Holden, Robin Pemantle, Yuval Peres, and Alex Zhai.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  Mathematical Statistics and Learning, 2(3/4):275–309, 2019.
  * [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.
  * [Kea98] M. Kearns.  Efficient noise-tolerant learning from statistical queries.  Journal of the ACM, 45(6):983–1006, 1998.
  * [KMMP19] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal.  Trace reconstruction: Generalized and parameterized.  In 27th Annual European Symposium on Algorithms, ESA 2019, volume 144 of LIPIcs, pages 68:1–68:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [Lev01a] Vladimir Levenshtein.  Efficient reconstruction of sequences.  IEEE Transactions on Information Theory, 47(1):2–22, 2001.
  * [Lev01b] Vladimir Levenshtein.  Efficient reconstruction of sequences from their subsequences or supersequences.  Journal of Combinatorial Theory Series A, 93(2):310–332, 2001.
  * [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.
  * [MS23] Kayvon Mazooji and Ilan Shomorony.  Substring density estimation from traces.  In IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023, pages 803–808. IEEE, 2023.
  * [Nar20] Shyam Narayanan.  Population recovery from the deletion channel: Nearly matching trace reconstruction bounds.  CoRR, abs/2004.06828, 2020.
  * [Nar21] Shyam Narayanan.  Improved algorithms for population recovery from the deletion channel.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1259–1278. SIAM, 2021.
  * [NP17] Fedor Nazarov and Yuval Peres.  Trace reconstruction with $\exp(O(n^{1/3}))$ samples.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1042–1046, 2017.
  * [NR21] Shyam Narayanan and Michael Ren.  Circular Trace Reconstruction.  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 18:1–18:18, 2021.
  * [PZ17] Yuval Peres and Alex Zhai.  Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 228–239. IEEE Computer Society, 2017.
  * [Rub23] Ittai Rubinstein.  Average-case to (shifted) worst-case reduction for the trace reconstruction problem.  261:Art. No. 102, 20, 2023.
  * [SB21] Jin Sima and Jehoshua Bruck.  Trace reconstruction with bounded edit distance.  In IEEE International Symposium on Information Theory, 2021.  Manuscript, available at https://arxiv.org/abs/2102.05372.