# Sparse Focus Network for Multi-Source Remote Sensing Data Classification

###### Abstract

Multi-source remote sensing data classification has emerged as a prominent
research topic with the advancement of various sensors. Existing multi-source
data classification methods are susceptible to irrelevant information
interference during multi-source feature extraction and fusion. To solve this
issue, we propose a sparse focus network for multi-source data classification.
Sparse attention is employed in Transformer block for HSI and SAR/LiDAR
feature extraction, thereby the most useful self-attention values are
maintained for better feature aggregation. Furthermore, cross-attention is
used to enhance multi-source feature interactions, and further improves the
efficiency of cross-modal feature fusion. Experimental results on the Berlin
and Houston2018 datasets highlight the effectiveness of SF-Net, outperforming
existing state-of-the-art methods.

Index Terms—  Multi-source remote sensing, Image classification, Sparse
attention mechanism, Hyperspectral imagery, Synthetic aperture radar, LiDAR.

##  1 Introduction

With the continuous development of various satellite sensors, multi-source
remote sensing image classification has gradually become one of the hot
research topics [2]. Multi-source remote sensing data classification refers to
the process of labeling pixels using data from different sensors, such as
hyperspectral image (HSI), synthetic aperture radar (SAR), and light detection
and ranging (LiDAR) [3]. Multi-source data classification has a wide range of
applications in disaster assessment [4], urban planning [5] and vegetation
monitoring [6].

In this paper, we mainly focus on HSI-SAR/LiDAR data classification. HSI
provides rich spectral information, SAR sensor is sensitive to the shape and
structure of ground objects, and LiDAR provides detailed height information of
ground objects. Recently, many deep learning-based methods have been proposed
for multi-source data classification. By introducing attention mechanisms [7,
8]. Wang et al. [7] employed bilinear attention fusion for HSI and LiDAR data
joint classification. Mohla et al. [8] used the self-attention and cross-
attention for multi-source remote sensing data classification. These methods
automatically learn the important information from the input data, thereby
improving model performance. Although attention mechanisms have achieved
excellant performance in multi-source data classification, they still have
some limitations, such as being susceptible to irrelevant information
interference during information interaction.

To address the issue, this study introduces a sparse attention mechanism to
optimize the model’s feature interaction process. Sparse attention reduces
interference from irrelevant features, retaining only the most relevant self-
attention values. To this end, we proposed a Sparse Focus Network (SF-Net) for
HSI-SAR/LiDAR data classification. Specifically, sparse attention is employed
in Transformer block for HSI and SAR/LiDAR feature extraction, thereby the
most useful self-attention values are maintained for better feature
aggregation. In addition, cross-attention is used to enhance multi-source
feature interactions, and further improves the efficiency of cross-modal
feature fusion. Extensive experimental results on the Berlin and Houston2018
datasets demonstrate the superior classification performance over existing
state-of-the-art methods.

Fig. 1: Overview of the proposed SF-Net for HSI and LiDAR/SAR classification.
Fig. 2: Classification results of different methods for the Berlin dataset.
(a) The ground truth. (b) TBCNN. (c) FusAtNet. (d) ExViT. (e) The proposed SF-
Net.

##  2 Methodology

Our proposed SF-Net framework for the classification of HSI and SAR/LiDAR is
depicted in Figure 1. SF-Net consists of the feature extraction module and
cross-attention fusion module. For HSI feature extraction, PCA is first
employed for spectral-dimension reduction, and 3D convolution is employed. For
SAR/LiDAR feature extraction, 2D convolution is employed. The critical part in
feature extraction is the Sparse Transformer Block (STB), and the STB is
repeated three times. Finally, features from HSI and SAR/LiDAR are fed into
the Cross-Attention Fusion Block (CAFB). The outputs of CAFB are transformed
into the classification results via fully connected layer.

It should be noted that the structure of STB is similar to the standard
Transformer block [9]. The main difference between the STB and standard
Transformer block is that STB utilizes sparse attention.

###  2.1 Sparse Attention

The sparse attention’s purpose is to dynamically retain crucial attention
scores for each query, boosting feature aggregation efficiency. This mechanism
achieves dynamic selection and sparsity in self-attention values, reducing
interference from irrelevant information and optimizing the model’s
performance in multi-source remote sensing image classification.

Fig. 1 illustrates the details of sparse attention. Given an input matrix
$X\in\mathbb{R}^{N\times D}$, where $N$ represents the number of tokens, and
$D$ denotes the dimensionality of each token, we utilize three fully connected
layers to derive the query $Q\in\mathbb{R}^{N\times D}$, key
$K\in\mathbb{R}^{N\times D}$, and value $V\in\mathbb{R}^{N\times D}$.

Afterward, we perform matrix multiplication on $Q$ and $K$, followed by a
selection operation. For each attention matrix $M_{\gamma}$, the parameter
$k_{\gamma}$ is determined by the following formula:

$k_{\gamma}=\lfloor\alpha\cdot N\rfloor,$ (1)

where $\alpha$ takes values of 1/2, 2/3, 3/4, 4/5, and $n$ is set to 4. This
formula ensures a varied sparsity level for each $M_{\gamma}$, where $\gamma$
ranges from 1 to $n$.

The selection operation retains the top $k_{\gamma}$ largest values while
setting the remaining values to 0. Consequently, this process results in the
creation of multiple attention matrices with distinct sparsity levels,
collectively denoted as $M_{\gamma}\in\mathbb{R}^{N\times N}$, Each
$M_{\gamma}$ within the set captures unique attention patterns. To elaborate
further, the acquisition of $M_{\gamma}$ is detailed as follows:

$\text{Score}=\frac{(QK^{T})}{\sqrt{D}}$ (2)
$M_{\gamma,ij}^{\prime}=\begin{cases}\text{Score}_{ij},&\text{if }j\text{ is
in the top }k_{\gamma}\text{ values}\\\ -\infty,&\text{if
}\text{otherwise}\end{cases}$ (3)
$M_{\gamma,i}=\text{softmax}(M_{\gamma,i}^{\prime})$ (4)

where the softmax function transforms the values in each row of
$M_{\gamma,i}^{\prime}$ into a probability distribution.

For each $M_{\gamma}$, the subsequent step entails performing matrix
multiplication between the acquired $M_{\gamma}$ and the value matrix $V$.
Finally, generate the output result $Z$. The detailed process is outlined as
follows:

$Z=\sum_{\gamma=1}^{n}Wt_{\gamma}\cdot M_{\gamma}V$ (5)

where $Wt_{\gamma}$ is a learnable weight parameter.

###  2.2 Cross-Attention Feature Fusion

In order to attain more accurate classification results, it is crucial to
effectively fuse multi-source features. The thoughtful design of feature
interactions allows the multi-source features to complement each other
effectively, thereby improving the discriminative capability for ground
objects and ultimately achieving superior classification performance.
Consequently, we utilize the cross-attention [10] mechanism to facilitate the
fusion of features between both modalities.

The details of the Cross-Attention Fusion Block (CAFB) is shown in Fig. 1.
Given the input hsi feature matrix $T_{\textrm{H}}\in\mathbb{R}^{N\times D}$
and LiDAR/SAR features matrix $T_{\textrm{X}}\in\mathbb{R}^{N\times D}$, the
entire execution process of CB is as follows.

$T_{H}^{\prime},T_{X}^{\prime}=\textrm{CA}(\textrm{LN}(T_{H}),\textrm{LN}(T_{X}))$
(6)
$T_{H}^{\prime\prime}=\textrm{FFN}(\textrm{LN}(T_{H}+T_{H}^{\prime}))+(T_{H}+T_{H}^{\prime})$
(7)
$T_{X}^{\prime\prime}=\textrm{FFN}(\textrm{LN}(T_{X}+T_{X}^{\prime}))+(T_{H}+T_{H}^{\prime})$
(8)
$T_{\textrm{out}}=\textrm{Concat}(T_{H}^{\prime\prime},T_{X}^{\prime\prime})$
(9)

where $T_{H}^{\prime}$ and $T_{X}^{\prime}$ serve as residuals to $T_{H}$ and
$T_{X}$, respectively, to enhance the model’s performance and learning
capability. $T_{\textrm{out}}$ represents the final output of the entire CAFB.

The details of the Cross Attention (CA) are illustrated in Fig. 1. Similar to
the standard attention computation, the key difference lies in comparing the
query from the $\overline{T}_{H}$ with the key from $\overline{T}_{X}$ to
obtain attention scores. Subsequently, the values $V_{X}$ derived from
$\overline{T}_{X}$ are used to produce the final result $T_{X}^{\prime}$ based
on the obtained attention. The process of obtaining $T_{H}^{\prime}$ and
$T_{X}^{\prime}$ is depicted as follows.

$T_{H}^{\prime}=\textrm{softmax}(\frac{Q_{X}K_{H}^{T}}{\sqrt{D}})V_{H}$ (10)
$T_{X}^{\prime}=\textrm{softmax}(\frac{Q_{H}K_{X}^{T}}{\sqrt{D}})V_{X}$ (11)

where $Q_{H}$, $K_{H}$, and $V_{H}$ are obtained from $T_{H}$ through three
fully connected layers, and $Q_{X}$, $K_{X}$, and $V_{X}$ follow a similar
process.

Table 1: Classification Performance (%) of Different Models on the Berlin Dataset. Class | TBCNN | Fusatnet | ExViT | SF-Net
---|---|---|---|---
Forest | 81.75 | 86.24 | 78.01 | 74.75
Residential area | 76.26 | 91.38 | 74.05 | 91.30
Industrial area | 39.67 | 19.76 | 39.48 | 34.36
Low plants | 49.78 | 20.00 | 84.15 | 65.75
Soil | 89.42 | 48.72 | 88.03 | 80.13
Allotment | 54.36 | 38.89 | 70.00 | 26.05
Commercial area | 4.65 | 18.47 | 38.18 | 28.23
Water | 41.93 | 29.61 | 56.41 | 38.24
OA | 67.60 | 70.91 | 72.63 | 74.89
Table 2: Classification Performance (%) of Different Models on the Huston2018 Dataset. Class | TBCNN | Fusatnet | ExViT | SF-Net
---|---|---|---|---
Health grass | 94.84 | 96.28 | 93.65 | 83.07
Stressed grass | 92.60 | 93.45 | 95.44 | 96.07
Artificial turf | 100.00 | 100.00 | 100.00 | 100.00
Evergreen trees | 98.80 | 98.33 | 98.52 | 92.78
Deciduous trees | 97.12 | 99.11 | 99.25 | 79.83
Bare earth | 99.61 | 100.00 | 99.92 | 98.54
Water | 100.00 | 100.00 | 100.00 | 99.47
Residential buildings | 93.21 | 97.90 | 96.88 | 88.66
Non-residential buildings | 91.30 | 93.41 | 94.87 | 99.14
Roads | 61.06 | 74.56 | 80.51 | 87.98
Sidewalks | 75.91 | 82.94 | 80.27 | 76.95
Crosswalks | 85.31 | 84.65 | 96.76 | 33.02
Major thoroughfares | 72.77 | 86.90 | 82.11 | 89.98
Highways | 95.86 | 97.59 | 84.10 | 83.24
Railways | 99.78 | 99.71 | 99.81 | 97.25
Paved parking lots | 90.74 | 98.08 | 99.08 | 92.68
Unpaved parking lots | 100.00 | 100.00 | 100.00 | 98.25
Cars | 98.47 | 97.11 | 97.56 | 89.93
Trains | 99.90 | 99.63 | 99.90 | 96.97
Stadium seats | 99.92 | 99.93 | 99.94 | 98.13
OA | 86.95 | 91.52 | 91.87 | 92.74

##  3 Experimental Results and Analysis

To verify the effectiveness of the proposed model, extensive experiments are
carried out on the Berlin dataset and Houston 2018 dataset. Berlin dataset is
used for HSI and SAR data classification, encompassing both urban and rural
areas in Berlin. The Berlin dataset comprises HSI and SAR images. The HSI
image has a resolution of 797$\times$220 pixels, covering a wavelength range
from 400 to 2500 nm with 244 spectral bands. In contrast, the SAR image has a
resolution of 1723$\times$476 pixels. Both images were captured in urban and
rural areas of Berlin, Germany. The Houston dataset includes HSI and LiDAR
images. The HSI image consists of 48 spectral bands covering a wavelength
range from 380 to 1050 nm. The LiDAR image contains 3 bands. This dataset
spans the campus of the University of Houston and its surrounding urban areas
in Houston, Texas, USA. It was part of the 2018 IEEE GRSS Data Fusion
Competition.

We compare the proposed SF-Net with three state-of-the-art methods, including
TBCNN [11] , FusAtNet [8] and ExViT [12]. The OA values of all methods are
presented in Table 1 and 2. As can be observed that the OA value of the
proposed SF-Net reaches 74.89% on the Berlin dataset. On the Houston2018
dataset, the OA value of the proposed SF-Net reaches 92.74%, significantly
outperforming the other methods. Fig. 2 illustrates the classification results
for the Berlin dataset. As can be seen that the result of the proposed SF-Net
is the closest to the human-labeled ground truth. Both the quantitative and
qualitative assessments demonstrate the exceptional performance of the
proposed SF-Net in multi-source remote sensing data classification.

##  4 Conclusion

In this paper, we propose SF-Net for multi-source remote sensing data
classification, addressing the challenges associated with information overload
and irrelevant feature interference. Sparse attention is employed in
Transformer block for HSI and SAR/LiDAR feature extraction, thereby the most
useful self-attention values are maintained for better feature aggregation. In
addition, cross-attention is used to enhance multi-souce feature interactions,
and further improves the efficiency of cross-modal feature fusion.
Experimental results on the Houston 2018 and Berlin datasets highlight the
effectiveness of SF-Net, outperforming existing state-of-the-art methods.

## References

  * [1]
  * [2] G. Zhao, Q. Ye, L. Sun, Z. Wu, C. Pan, and B. Jeon. “Joint classification of hyperspectral and LiDAR data using a hierarchical CNN and Transformer,” IEEE Transactions on Geoscience and Remote Sensing, vol. 61, pp. 1–16, 2023.
  * [3] J. Wang, F. Gao, J. Dong, and Q. Du, “Adaptive dropblock-enhanced generative adversarial networks for hyperspectral image classification,” IEEE Transactions on Geoscience and Remote Sensing, vol. 59, no. 6, pp. 5040–5053, 2021.
  * [4] H. Wang et al., “Multi-source remote sensing intelligent characterization technique-based disaster regions detection in high-altitude mountain forest areas,” IEEE Geoscience and Remote Sensing Letters, vol. 19, pp. 1–5, 2022.
  * [5] Q. Cheng, Q. Chen, Y. Li and B. Cao, “Analysis of the influence of sky view factor on urban surface temperature based on multi-source data,” In IGARSS 2021, pp. 6952–6955.
  * [6] Y. Xu, M. Zhang, E. Yu, Y. Hou, C. Yang and S. Deng, “Assessing temporal and spatial variations of vegetation degradation in southwest China based on multi-source remote sensing data,” In IGARSS 2022, pp. 6005–6008.
  * [7] M. Wang, F. Gao, J. Dong, H. Li, and Q. Du, “Nearest neighbor-based contrastive learning for hyperspectral and LiDAR data classification,” IEEE Transactions on Geoscience and Remote Sensing, vol. 61, pp. 1–16, 2023.
  * [8] S. Mohla, S. Pande, B. Banerjee, and S. Chaudhuri, “Fusatnet: Dual attention based spectrospatial multi-modal fusion network for hyperspectral and LiDAR classification,” CVPR Workshop 2020, pp. 416-425.
  * [9] A. Dosovitskiy, L. Beyer, A. Kolesnikov, et al. “An image is worth 16x16 words: Transformers for image recognition at scale,” ICLR 2021, pp. 1–12.
  * [10] H. Kim, S. Yu, S. Yuan, and C. Tomasi, “Cross-attention Transformer for video interpolation,” ACCV 2022, pp. 320–-337.
  * [11] X. Xu, W. Li, Q. Ran, Q. Du, L. Gao, and B. Zhang, “Multisource remote sensing data classification based on convolutional neural network,” IEEE Transactions on Geoscience and Remote Sensing, vol. 56, no. 2, pp. 937-–949, 2017.
  * [12] J. Yao, B. Zhang, C. Li, D. Hong, and J. Chanussot, “Extended vision Transformer (ExViT) for land use and land cover classification: A multimodal deep learning framework,” IEEE Transactions on Geoscience and Remote Sensing, vol. 61, pp. 1–15, 2023.


# Limitations of Mean-Based Algorithms for Trace Reconstruction at Small
Distance

Elena Grigorescu Purdue University, Email: {elena-g<EMAIL_ADDRESS>Research supported in part by NSF CCF-1910659 and NSF CCF-1910411 Madhu Sudan
Harvard University, Email<EMAIL_ADDRESS>Research supported in part by
a Simons Investigator Award and NSF Award CCF 1715187. Minshen
Zhu11footnotemark: 1

###### Abstract

Trace reconstruction considers the task of recovering an unknown string
$x\in\\{0,1\\}^{n}$ given a number of independent “traces”, i.e., subsequences
of $x$ obtained by randomly and independently deleting every symbol of $x$
with some probability $p$. The information-theoretic limit of the number of
traces needed to recover a string of length $n$ are still unknown. This limit
is essentially the same as the number of traces needed to determine, given
strings $x$ and $y$ and traces of one of them, which string is the source.

The most studied class of algorithms for the worst-case version of the problem
are “mean-based” algorithms. These are a restricted class of distinguishers
that only use the mean value of each coordinate on the given samples. In this
work we study limitations of mean-based algorithms on strings at small Hamming
or edit distance.

We show on the one hand that distinguishing strings that are nearby in Hamming
distance is “easy” for such distinguishers. On the other hand, we show that
distinguishing strings that are nearby in edit distance is “hard” for mean-
based algorithms. Along the way we also describe a connection to the famous
Prouhet-Tarry-Escott (PTE) problem, which shows a barrier to finding explicit
hard-to-distinguish strings: namely such strings would imply explicit short
solutions to the PTE problem, a well-known difficult problem in number theory.

Our techniques rely on complex analysis arguments that involve careful
trigonometric estimates, and algebraic techniques that include applications of
Descartes’ rule of signs for polynomials over the reals.

##  1 Introduction

In the trace reconstruction problem, a string $x\in\\{0,1\\}^{n}$ is sent over
a deletion channel which deletes each entry independently with probability
$p\in[0,1)$, resulting in a trace $\tilde{x}\in\\{0,1\\}^{\ell}$ of smaller
length. The goal is to reconstruct $x$ exactly from a small set of independent
traces. The trace reconstruction problem was introduced by Batu et al.
[BKKM04] motivated by a natural problem in computational biology in which a
common ancestor DNA sequence is sought from a set of similar DNA sequences
that might have resulted from the process of random deletions in the ancestor
DNA. The information-theoretic limits and tight complexity of this problem
have proven elusive so far, despite significant followup interest in a variety
of relevant settings [BKKM04, KM05, VS08, HMPW08, MPV14, PZ17, NP17, DOS17,
GM17, HPP18, HL20, HHP18, GM19, CRGM19, KMMP19, BLS20, CDL+20, Cha20, NR20].
The current upper bound in the worst-case formulation was recently improved by
Chase [Cha20] who showed that $\exp(\tilde{O}(n^{1/5}))$ traces are sufficient
for reconstruction, thus beating the previous record of $\exp(O(n^{1/3}))$
traces due to [NP17, DOS17]. However, the most general lower bound is only
${\tilde{\Omega}}(n^{3/2})$ [HL20, Cha19], hence leaving the status of the
problem widely open.

To gain more insight into the trace reconstruction problem we study the trace
distinguishing variant, in which given two string $x,y\in\\{0,1\\}^{n}$ the
algorithm receives traces from one of the two trace distributions and is
tasked to output the correct one. The trace distinguishing problem is
information theoretically equivalent to the classical trace reconstruction
problem [HMPW08]. From a computational standpoint, the same upper and lower
bounds as for the general problem hold for the trace distinguishing variant.

In this work we aim to get more insight into the worst-case trace
distinguishing problem from understanding the role of distance in the
complexity of the problem. We ask the following questions: Are all pairs of
strings that are close in Hamming distance easily distinguishable? Are all
pairs of strings that are close in edit distance easily distinguishable? Note
that the strings used for showing the lower bounds in [HL20, Cha19] only
differ in two locations and are indeed efficiently distinguishable (these were
the strings $x=(01)^{k}101(01)^{k}$ and $y=(01)^{k}011(01)^{k}$). On the other
hand, it is also reasonable to believe that trace distributions of strings
that are very different from each other are also easily distinguishable. In
fact, there exist “codes”, namely sets of strings that are very far from each
other, whose elements (codewords) lead to trace distributions that are very
easily distinguishable from each other [CRGM19, BLS20]. However, these are
existential results, revealing little explicit structure that may help in
further analysis.

Here we approach the above questions by analyzing a restricted class of
algorithms, namely mean-based. Mean-based algorithms only use the empirical
mean of individual bits, and hence they operate by disregarding the actual
samples, and computing only with the information given by the averages of each
bit $\tilde{x}_{i}$ over the sample set $S$ of independent traces, namely
$E_{S}(\tilde{x}_{i})$. While they appear restrictive, mean-based algorithms
are in fact a very powerful class of algorithms – the upper bounds of [DOS17,
NP17] are obtained via mean-based algorithms.

However, there exist strings $x,y\in\\{0,1\\}^{n}$ [DOS17, NP17] that mean-
based algorithms cannot distinguish with fewer than $\exp(\Omega(n^{1/3}))$
traces. This lower bounds is based on a result in complex analysis [BE97],
which only implies the existence of such strings $x$ and $y$, and not what
such strings would look like structurally.

Our main results here prove that there exist explicit strings
$x,y\in\\{0,1\\}^{n}$ at edit distance only $4$ for which every mean-based
algorithm requires a super-polynomial in $n$ number of samples. On the other
hand, we identify some structural properties of strings at low edit distance
that yield polynomial-time mean-based trace reconstruction. In [KR97, KMMP19]
the authors show that strings at small Hamming distance are efficiently
distinguishable. We complement these results by observing that they are
efficiently distinguishable even by mean-based algorithms. We believe that
understanding structural properties of explicit hard-to-distinguish strings
will eventually lead to a better understanding of the complexity of the trace
reconstruction problem.

We formalize our results next.

###  1.1 Our results

We start with an observation about strings at small Hamming distance.

######  Theorem 1.

Let $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ be two distinct strings
within Hamming distance $d$ from each other. There is a mean-based algorithm
which distinguishes between $\mathbf{x}$ and $\mathbf{y}$ with high
probability using $n^{O(d)}$ traces.

The result is a slight strengthening of a recent result of [KMMP19] who proved
exactly the same bounds for general algorithms. A weaker version was also
shown in [KR97, Sco97] where it is proved that strings at Hamming distance
$2k$ have distinct $k$-decks, i.e. multisets of all $n\choose k$ subsequences
of length $k$. Our contribution here is essentially to notice that the
techniques of [KR97, Sco97] imply that mean-based algorithms can in fact
distinguish such trace distributions (see Section B.2 of the appendix for a
more detailed discussion and the complete proof).

Our main results concern the negative results at small edit distance.

######  Theorem 2.

Assume the deletion probability $p=1/2$. There exist (explicit) strings
$\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ within edit distance 4 of
each other such that any mean-based algorithm requires
$\exp\left(\Omega(\log^{2}n)\right)$ traces to distinguish between
$\mathbf{x}$ and $\mathbf{y}$ with high probability.

Along the way, we also formalize a connection to the famous Prouhet-Tarry-
Escott (PTE) [Pro51, Dic13, Wri59] problem from number theory. The PTE problem
is related to classical variants of the Waring problem and problems about
minimizing the norm of cyclotomic polynomials, considered by Erdös and
Szekeres [ES59, BI94]. In fact, our explicit solution from Theorem 2 is based
on products of cyclotomic polynomials.

In the PTE problem, given an integer $k\geq 0$ one would like to find integer
solutions $\\{x_{1},x_{2},\ldots,x_{s}\\}$, and
$\\{y_{1},y_{2},\ldots,y_{s}\\}$ to the system
$\sum_{i\in[s]}x_{i}^{j}=\sum_{i\in[s]}y_{i}^{j}$, for all $j\in[k]$, with
$x_{i}\neq y_{j}$ for all $i,j\in[s]$. The goal is to find such solutions with
$s$ as small as possible compared to $k$. It is easy to show that $s\geq k+1$,
and a pigeon-hole counting argument shows the existence of solutions with
$s=O(k^{2})$ [Wri35]. With the additional constraint that the system is not
satisfied for degree $k+1$, solutions of size $s=O(k^{2}\log k)$ are known to
exist [Hua82]. However, all these are existential, non-constructive solutions,
and the only general explicit solutions have size $s=O(2^{k})$ (e.g., [Wri59,
BI94]).

We note that connections between the trace reconstruction problem and the PTE
problem have been previously made. In particular, Krasikov and Roditty [KR97]
noticed that pairs of strings that have the same $k$ decks yield solutions to
PTE systems.

As a consequence of our results we show that explicit strings that are
exponentially hard to distinguish by mean-based algorithms imply solutions of
small size to a PTE system.

######  Theorem 3.

Fix any $\varepsilon\in(0,1/3]$. Given distinct strings
$\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ such that any mean-based
algorithm requires $\exp\left(\Omega(n^{\varepsilon})\right)$ traces to
distinguish between $\mathbf{x}$ and $\mathbf{y}$, the following two sets
constitute a solution to the degree-$k$ PTE system

$\displaystyle D(\mathbf{x})=\left\\{i\colon x_{i}=1\right\\},\quad
D(\mathbf{y})=\left\\{i\colon y_{i}=1\right\\},$

with size $n=\left(k\log k\right)^{2/\varepsilon}$.

PTE systems appear to be intimately connected to the trace reconstruction
problem. Indeed, the analysis of mean-based algorithms often reduces to the
study Littlewood-type polynomials, namely polynomials with $\\{-1,0,1\\}$
coefficients, on the complex unit circle. This in turn often involves
understanding the multiplicity of the root $1$, which is again a questions
tightly related to the PTE problem (see discussion in Section 3).

We also note that weak versions of our results follow from simple applications
of the Descartes rule of signs [Des86]. As an application of this rule to
larger edit distances we also obtain the following theorem, formalized in
Section 5.

######  Theorem 4.

(Informal) Strings $x,y\in\\{0,1\\}^{n}$ with $d_{\textsf{E}}(x,y)=d\geq 1$
with some special block structures are distinguishable by mean-based
algorithms running in time $n^{O(d^{2})}.$ In particular, the statement holds
for every pair of strings at edit distance $2$.

###  1.2 Our techniques

#### The [DOS17, NP17] reduction to complex analysis

Our techniques focus on analyzing the modulus of Littlewood polynomials with
$\\{-1,0,1\\}$ coefficients over a shifted unit circle. The reduction to
complex analysis was established in [DOS17, NP17]. In particular, since a
mean-based algorithm only works with $E(\tilde{x}_{i})$ for each $i$, they
define the associated polynomials
$P_{\mathbf{x}}(z)=\sum_{j=0}^{n-1}E_{j}(\mathbf{x})\cdot z^{j}$ and the
related polynomial
$Q_{\mathbf{x}}(p+qz)=q^{-1}P_{\mathbf{x}}(z)=\sum_{k=0}^{n-1}x_{k}\cdot\left(p+qz\right)^{k}$
(and hence $Q_{\mathbf{x}}(z)=\sum_{k=0}^{n-1}x_{k}\cdot z^{k}$), which is
obtained from writing the $E_{j}$’s explicitly as

$\displaystyle
E_{j}(\mathbf{x})=\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}\left[\tilde{x}_{j}\right]=\sum_{k=0}^{n-1}\Pr\left[\tilde{x}_{j}\textup{
comes from }x_{k}\right]\cdot
x_{k}=\sum_{k=0}^{n-1}\binom{k}{j}p^{k-j}q^{j+1}\cdot x_{k},$

Here $p$ is the deletion probability and $q=1-p.$ Then [DOS17, NP17] show that
the sample complexity upper bound for mean-based algorithms is roughly (up to
squaring) the inverse of

$\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B\left(p;q\right)\right\\}$

where $\partial B\left(p;q\right)$ is the complex unit circle shifted to the
complex circle of radius $q$ centered at $p$. Hence, the problem reduces to
understanding the maximum modulus of a polynomial on a shifted circle. For
completeness we include the details of the reduction in Appendix A. Note that
all coefficients of $Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$ belong to
$\\{-1,0,1\\}.$

#### Applications of Descartes’ Rule of Signs

Here we relate the supremum of $|Q(w)|$ over the shifted complex circle to the
multiplicity of the root $w=1$ of the polynomial $Q(w)$. Specifically, we show
that as long as $w=1$ is a root with multiplicity no more than $k$, the
supremum over the shifted complex circle is at least $n^{-O(k^{2})}$.

######  Theorem 5.

Let $f(z)$ be a polynomial of degree $n$ with coefficients in
$\left\\{-1,0,1\right\\}$. Suppose $z=1$ is a root of $f(z)$ with multiplicity
at most $k$. Let $0<p<1$ and $q=1-p$. Then

$\displaystyle\sup\left\\{\left|f(z)\right|\colon z\in\partial
B\left(p;q\right)\right\\}\geq\frac{1}{2}(4n^{k+2})^{-k}=n^{-O(k^{2})}.$

It is then desirable to upper bound the multiplicity of zero at 1 for various
polynomials. Descartes’ rule of sign changes provides a convenient tool to
achieve this.

######  Lemma 1 ([Des86], Theorem 36, Chapter 1, Part Five of [PS97]).

Let $Z(p)$ be the number of real positive roots of the real polynomial $p(x)$
(counting with multiplicity) and $C(p)$ the number of changes of sign of the
sequence of its coefficients. We then have $C(p)\geq Z(p)$.

We note that prior work that we are aware of on understanding the structure of
polynomials with many roots at $1$ (e.g., [Erd14, Erd19]) do not appear to
imply our bounds on the complex unit circle.

#### Remark

If $p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots+a_{n}x^{n}$ is a polynomial, we say a
pair $(i,j)$ ($0\leq i<j\leq n$) is a _sign change_ if $a_{i}a_{j}<0$ and
$a_{i+1}=a_{i+2}=\ldots=a_{j-1}=0$. $C(p)$ exactly counts the number of such
pairs $(i,j)$.

We use this rule to prove the formal version of Theorem 4, namely Theorem 8.
We also use it to give an extremely simple proof of a weaker version of
Theorem 1, namely, Corollary 2.

#### Complex analysis over shifted circles: the strong version of our results

A main stepping stone in our derivation of Theorem 1 and Theorem 4 is that low
multiplicity of the root $w=1$ implies large supremum over the shifted complex
circle (i.e. Theorem 5). The idea is to find a point on the shifted circle
that has a very small (but carefully chosen) distance to $1$, and argue that
the polynomial has large modulus at that point. The analysis is mostly
elementary, including manipulations and estimations of trigonometric
functions, and deriving bounds on the coefficients and derivatives of certain
polynomials.

For the negative result (i.e. Theorem 2), the difficulty comes from the fact
that the converse of Theorem 5 is not true. In fact, the strongest barrier is
the fact that constructing small-size solutions to high-degree PTE systems is
a well-known difficult problem in number theory. The non-constructive methods
in [BE97] and [Wri35] do not appear to be the correct tools either, because of
the edit distance constraint, which cannot be accounted for in their
arguments. Our construction is inspired by properties of product of cyclotomic
polynomials and their relation to PTE solutions with special structures.

###  1.3 Related work

The first formulations of the problem were proposed by [Lev01b, Lev01a] and
the precise formulation we study here were developed in [BKKM04, HMPW08],
motivated by the connection with DNA reconstruction. DNA sequencing recently
motivated the model of “coded” trace reconstruction [CRGM19, BLS20] in which
the goal is to reconstruct codewords of a known code, rather than an arbitrary
string. These papers show almost optimal such construction of codes with very
fast reconstruction, in some cases even using constantly many traces.

Besides the worst-case trace reconstruction discussed earlier in the
introduction, a well-studied variant has been the average case trace
reconstruction problem studied in [HMPW08, PZ17, MPV14, HPP18]. Here, the best
current lower bound is $\Omega(\log^{5/2}n)$ [HL20, Cha19], and best
algorithms run in time $\exp\left(O(\log^{1/3}n)\right)$.

A recent intriguing result [CDL+20] considers the smooth variant, which is an
intermediate model between the worst-case and the average-case models, and
shows reconstruction can be done efficiently when receiving traces from
arbitrary worst-case strings that are perturbed in such a way that each
coordinate is replaced by a uniformly random bit.

Other variants consider string reconstruction from the multiset of substrings
[GM17, GM19], population recovery variants [BCF+19], matrix reconstruction,
and parametrized algorithms [KMMP19], and circular trace reconstruction
[NR20].

###  1.4 Organization of the paper

In Section 2 we develop the necessary notations and basic facts. In Section 3
we prove Theorem 5 which is a key factor in our analysis, and use it to prove
Theorem 3. In Section B we prove Theorem 1. In Section 4 we prove Theorem 7,
which is a more concrete version of Theorem 2. In Section 5 we prove Theorem
8, which is an equivalent and more concrete version of Theorem 4. In Appendix,
we also explain how to reduce the analysis of mean-based algorithms to
understanding the supremum of certain polynomials over a shifted complex
circle.

##  2 Preliminaries

Given $z\in\mathbb{C}$ and $r\in\mathbb{R}_{\geq 0}$, we write

$\displaystyle B(z;r)\coloneqq\left\\{w\in\mathbb{C}\colon|w-z|\leq
r\right\\}$

for the disk centered at $z$ with radius $r$, and write $\partial B(z;r)$ for
its boundary.

Let $p(w)=a_{0}+a_{1}w+\ldots+a_{n}w^{n}$ be a polynomial where the
coefficients are real. Let $A\subseteq\mathbb{C}$ be a set. We define the
following norms.

$\displaystyle\left\lVert
p\right\rVert_{1}=\sum_{j=0}^{n}|a_{j}|,\quad\left\lVert
p\right\rVert_{2}=\left(\sum_{j=0}^{n}a_{j}^{2}\right)^{1/2},\quad\left\lVert
p\right\rVert_{A}=\sup_{w\in A}|p(w)|.$

When $A=\partial B(0;1)$ is the complex unit circle, we also write
$\left\lVert p\right\rVert_{A}=\left\lVert p\right\rVert_{\infty}$. These
norms are connected by the following inequalities.

######  Lemma 2.

Let $p$ be a degree-$n$ polynomial with real coefficients. Then

$\displaystyle\frac{1}{\sqrt{n+1}}\cdot\left\lVert
p\right\rVert_{1}\leq\left\lVert p\right\rVert_{2}\leq\left\lVert
p\right\rVert_{\infty}\leq\left\lVert p\right\rVert_{1}.$

###### Proof.

The first and third inequalities are applications of Cauchy-Schwartz and the
triangle inequality, respectively. The second inequality comes from the
following identity

$\displaystyle\left\lVert
p\right\rVert_{2}^{2}=\frac{1}{2\pi}\int_{0}^{2\pi}\left|p\left(e^{i\theta}\right)\right|^{2}d\theta,$

where the right-hand-side is clearly upper bounded by $\left\lVert
p\right\rVert_{\infty}^{2}$. ∎

We will use $p$ for the deletion probability and $q=1-p$. In this paper $p$
and $q$ will be constants. Given a string
$\mathbf{a}\in\left\\{0,1\right\\}^{n}$, a trace
$\tilde{\mathbf{a}}\in\left\\{0,1\right\\}^{\leq n}$ is a subsequence of
$\mathbf{a}$ obtained by deleting each bit of $\mathbf{a}$ independently with
probability $p$. The length of $\tilde{\mathbf{a}}$ is denoted by
$|\tilde{\mathbf{a}}|$. For $0\leq j\leq n-1$, the $j$-th bit of $\mathbf{a}$
and $\tilde{\mathbf{a}}$ are written as $a_{j}$ and $\tilde{a}_{j}$,
respectively. The distribution of $\tilde{\mathbf{a}}$ is denoted by
$\mathcal{D}_{\mathbf{a}}$. We also associate to $\mathbf{a}$ the following
polynomial

$\displaystyle Q_{\mathbf{a}}(w)\coloneqq
a_{0}+a_{1}w+a_{2}w^{2}+\ldots+a_{n-1}w^{n-1}.$

The degree of $Q_{\mathbf{a}}$ is at most $n-1$.

For strings $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$, we will write
$d_{\textsf{H}}(x,y)$ for the Hamming distance between $\mathbf{x}$ and
$\mathbf{y}$, where $d_{\textsf{H}}(\mathbf{x},\mathbf{y})=|\\{i\in[n]\colon
x_{i}\neq y_{i}\\}|$; and write $d_{\textsf{E}}(\mathbf{x},\mathbf{y})$ for
the edit distance between $\mathbf{x}$ and $\mathbf{y}$, namely the minimum
number of insertions and deletions that transform $\mathbf{x}$ into
$\mathbf{y}$.

##  3 Large supremum from low multiplicity of root $1$

Fix two strings $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ and denote
$f(w)=Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$. We are interested in $\sup|f(w)|$
where $w$ is on the circle $\partial B\left(p;q\right)$. It turns out that we
can lower bound this supremum by upper bounding the multiplicity of zero of
$f(w)$ at 1.

######  Lemma 3 (Lemma 5.4 of [BEK99]).

Suppose

$\displaystyle p(x)=\sum_{j=0}^{n}a_{j}x^{j},$
$\displaystyle\left|a_{j}\right|\leq 1,a_{j}\in\mathbb{C}$ $\displaystyle
p(x)=(x-1)^{k}q(x),\quad q(x)=\sum_{j=0}^{n-k}b_{j}x^{j},$ $\displaystyle
b_{j}\in\mathbb{C}.$

Then

$\displaystyle\sum_{j=0}^{n-k}\left|b_{j}\right|\leq(n+1)\left(\frac{en}{k}\right)^{k}.$

######  Lemma 4.

Let $f(z)=\sum_{k=0}^{n}a_{k}z^{k}$ be a polynomial. Let
$u(t)=\operatorname{Re}f(z(t))$ be a real-valued function, where
$z(t)=p+qe^{it}$. Then

$\displaystyle\left|u^{\prime}(t)\right|\leq
q\cdot\sum_{k=0}^{n}k\left|a_{k}\right|\leq
qn\cdot\sum_{k=0}^{n}\left|a_{k}\right|.$

###### Proof.

Write $z(t)=x(t)+y(t)i$ and $f(x+yi)=u(x,y)+v(x,y)i$ where

$\displaystyle x(t)=p+q\cos t,\quad y(t)=q\sin t.$

By Cauchy-Schwarz we have that

$\displaystyle\left|u^{\prime}(t)\right|$ $\displaystyle=\left|\frac{\partial
u}{\partial x}\cdot\frac{\partial x}{\partial t}+\frac{\partial u}{\partial
y}\cdot\frac{\partial y}{\partial t}\right|\leq\left(\left(\frac{\partial
u}{\partial x}\right)^{2}+\left(\frac{\partial u}{\partial
y}\right)^{2}\right)^{1/2}\left(\left(\frac{\partial x}{\partial
t}\right)^{2}+\left(\frac{\partial y}{\partial t}\right)^{2}\right)^{1/2}$
$\displaystyle=\left(\left(\frac{\partial u}{\partial
x}\right)^{2}+\left(\frac{\partial u}{\partial
y}\right)^{2}\right)^{1/2}\left((-q\sin t)^{2}+(q\cos t)^{2}\right)^{1/2}$
$\displaystyle=q\cdot\left(\left(\frac{\partial u}{\partial
x}\right)^{2}+\left(\frac{\partial u}{\partial y}\right)^{2}\right)^{1/2}.$

Since $f$ satisfies the Cauchy-Riemann equations (see [Lan13] for example), we
have that

$\displaystyle f^{\prime}(x+yi)=\frac{\partial u}{\partial x}-\frac{\partial
u}{\partial y}i.$

Therefore $|u^{\prime}(t)|\leq q\cdot|f^{\prime}(z)|\leq
q\cdot\sum_{k=0}^{n}k|a_{k}|$, where the last inequality is due to the
triangle inequality. ∎

We can now prove Theorem 5, which will be useful to obtain several of our
results in their weaker form. The proof also works for the more general class
of polynomials with bounded integer coefficients.

###### Proof of Theorem 5.

We can write $f(z)=(z-1)^{k}\cdot g(z)$ where $g(z)$ is a polynomial and
$g(1)\neq 0$. It is not hard to see that $g(z)$ is a polynomial with integer
coefficients, hence $g(1)$ is an integer and $|g(1)|\geq 1$.

Since the coefficients of $f$ are absolutely bounded by $1$, by Lemma 3 the
absolute values of the coefficients of $g(z)$ sum up to at most $n^{k+1}$.

Define a real-valued function $u(t)=\operatorname{Re}g\left(p+qe^{it}\right)$.
We have $|u(0)|=|\operatorname{Re}g(1)|=|g(1)|\geq 1$. Lemma 3 and Lemma 4
together give the bound $|u^{\prime}(t)|\leq q\cdot n^{k+2}$. Now we take
$\theta=1/2qn^{k+2}$ and $z=p+qe^{i\theta}$ so that

$\displaystyle|z-1|=q\left|e^{i\theta}-1\right|=2q\sin\frac{\theta}{2}>\frac{q\theta}{2}=\frac{1}{4n^{k+2}}.$

Here we uses the fact $\sin x>x/2$ for small $x$. The Mean Value Theorem
implies that for some $\tilde{t}\in(0,\theta)$ we have

$\displaystyle\left|g(z)\right|\geq\left|\operatorname{Re}g(z)\right|=\left|u(\theta)\right|\geq\left|u(0)\right|-\theta\left|u^{\prime}\left(\tilde{t}\right)\right|\geq
1-\frac{1}{2qn^{k+2}}\cdot qn^{k+2}=\frac{1}{2}.$

Overall we have

$\displaystyle\left|f(z)\right|$
$\displaystyle=|z-1|^{k}\cdot|g(z)|\geq\left(\frac{1}{4n^{k+2}}\right)^{k}\cdot\frac{1}{2}=n^{-O(k^{2})}.$

Since $z\in\partial B\left(p;q\right)$,
$\sup\left\\{\left|f(z^{\prime})\right|\colon z^{\prime}\in\partial
B\left(p;q\right)\right\\}\geq\left|f(z)\right|\geq n^{-O(k^{2})}$. ∎

###  3.1 Connection to the Prouhet-Tarry-Escott problem

The following is a classical statement about the PTE problem.

######  Theorem 6.

(e.g. [BI94]) The following are equivalent:

  * •

$\sum_{i=1}^{s}\alpha_{i}^{j}=\sum_{i=1}^{s}\beta_{i}^{j}$, for $1\leq j\leq
k$, and $\sum_{i=1}^{s}\alpha_{i}^{k+1}\neq\sum_{i=1}^{s}\beta_{i}^{k+1}$.

  * •

$\sum_{i=1}^{s}x^{\alpha_{i}}-\sum_{i=1}^{s}x^{\beta_{i}}=(x-1)^{k+1}q(x)$
where $q\in\mathbb{Z}[x]$ and $q(1)\neq 0.$

This connection allows us to prove Theorem 3.

See 3

###### Proof.

Assume $D(\mathbf{x})$ and $D(\mathbf{y})$ do not constitute a solution to the
degree-$k$ PTE system. That implies $(w-1)^{k+1}\nmid
Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$, i.e. the multiplicity of zero of
$Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$ at 1 is at most $k$. By Theorem 5, we
have

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B(p;q)\right\\}\geq n^{-O(k^{2})}=\exp\left(-O(k^{2}\log
n)\right).$

However, we also have

$\displaystyle n^{\varepsilon}=\left(k\log k\right)^{2},\quad k^{2}\log
n=\frac{2}{\varepsilon}\cdot k^{2}\left(\log k+\log\log k\right),$

which means $k^{2}\log n=o(n^{\varepsilon})$ as $k,n\rightarrow\infty$.
Therefore $\exp\left(o(n^{\varepsilon})\right)$ traces are sufficient to
distinguish between $\mathbf{x}$ and $\mathbf{y}$, which is a contradiction. ∎

##  4 Hard strings at edit distance 4

The goal of this section is to prove Theorem 2, and thus exhibit two strings
at edit distance $4$ such that every mean-based algorithm requires super-
polynomially many traces.

Before proving Theorem 2, we need the following lemma about estimation of
trigonometric functions.

######  Lemma 5.

The following bounds hold:

  1. 1.

For integer $d\geq 1$ and $\varphi$ such that
$\left|d\varphi\right|\leq\frac{\pi}{3}$, we have
$\cos\left(d\varphi\right)\leq\left(\cos\varphi\right)^{d}$.

  2. 2.

Let integer $d\geq 1$ and $\theta$ be such that
$\left|d\cdot\frac{\theta}{2}\right|<\frac{\pi}{3}$. Let
$w=\left(1+e^{i\theta}\right)/2$. Then
$\left|w^{d}-1\right|<2\left|\sin\left(\frac{d\theta}{4}\right)\right|$.

###### Proof.

  1. 1.

The inequality is trivially true when $d=1$. We also have

$\displaystyle\cos\left((d+1)\varphi\right)=\cos\left(d\varphi\right)\cos\varphi-\sin\left(d\varphi\right)\sin\varphi\leq\cos\left(d\varphi\right)\cos\varphi.$

The inequality is due to $\sin(d\varphi)\sin\varphi\geq 0$. Therefore an
induction on $d$ finishes the proof.

  2. 2.

We can write

$\displaystyle
w=\frac{1+\cos\theta}{2}+i\cdot\frac{\sin\theta}{2}=\cos\frac{\theta}{2}\left(\cos\frac{\theta}{2}+i\sin\frac{\theta}{2}\right),$

and

$\displaystyle
w^{d}=\left(\cos\frac{\theta}{2}\right)^{d}\cdot\left(\cos\frac{d\theta}{2}+i\sin\frac{d\theta}{2}\right).$

Therefore

$\displaystyle\left|w^{d}-1\right|^{2}$
$\displaystyle=\left(\left(\cos\frac{\theta}{2}\right)^{d}\cdot\cos\frac{d\theta}{2}-1\right)^{2}+\left(\left(\cos\frac{\theta}{2}\right)^{d}\cdot\sin\frac{d\theta}{2}\right)^{2}$
$\displaystyle=\left(\cos\frac{\theta}{2}\right)^{2d}-2\left(\cos\frac{\theta}{2}\right)^{d}\cos\frac{d\theta}{2}+1$
$\displaystyle=\left(\left(\cos\frac{\theta}{2}\right)^{d}-\cos\frac{d\theta}{2}\right)^{2}+\left(\sin\frac{d\theta}{2}\right)^{2}.$

By item (1), $\cos\left(d\theta/2\right)\leq\cos^{d}\left(\theta/2\right)$ and
hence

$\displaystyle\left|w^{d}-1\right|^{2}\leq\left(1-\cos\frac{d\theta}{2}\right)^{2}+\left(\sin\frac{d\theta}{2}\right)^{2}=2-2\cos\frac{d\theta}{2}=4\left(\sin\frac{d\theta}{4}\right)^{2},$

which implies $\left|w^{d}-1\right|\leq 2\left|\sin\frac{d\theta}{4}\right|$.

∎

We will prove the following theorem, which is a more concrete version of
Theorem 2.

######  Theorem 7.

Assume the deletion probability $p=1/2$. Let $k$ be an odd integer and
$n=\sum_{j=0}^{k}3^{j}$ be an even integer, and
$R(w)=\prod_{j=0}^{k}\left(1-w^{3^{j}}\right)$ be a polynomial of degree $n$.
Let $E_{n}(w)=\sum_{j=0}^{n/2}w^{2j}$. Then $Q_{\mathbf{e}}(w)\coloneqq
R(w)+E_{n}(w)$ is a 0/1-coefficient polynomial which corresponds to a string
$\mathbf{e}\in\left\\{0,1\right\\}^{n}$. Moreover, any two strings
$\mathbf{x}$, $\mathbf{y}$ of the form $\mathbf{x}=\mathbf{a}10\mathbf{e}$ and
$\mathbf{y}=\mathbf{a}\mathbf{e}01$ satisfy

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B(p;q)\right\\}\leq\exp\left(-\Omega(\log^{2}n)\right),$

where $\mathbf{a}$ is an arbitrary string of length $n$.

###### Proof.

$R(w)$ has the following properties: (1) The coefficients of $R$ belong to
$\left\\{-1,0,1\right\\}$ since each monomial occurs only once in the
expansion. (2) Odd-degree terms have negative signs, and even-degree terms
have positive signs. It follows that $R(w)+E_{n}(w)$ is a polynomial with 0/1
coefficients.

We can write

$\displaystyle P(w)$
$\displaystyle=Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)=w^{n}\left((w^{2}-1)Q_{\mathbf{e}}(w)-\left(w^{n+2}-1\right)\right)$
$\displaystyle=w^{n}(w^{2}-1)\left(Q_{\mathbf{e}}(w)-E_{n}(w)\right)$
$\displaystyle=w^{n}(w^{2}-1)R(w).$

Consider a point $w=\left(1+e^{i\theta}\right)/2$ on the circle $\partial
B(1/2;1/2)$, where $\theta\in[-\pi,\pi]$. We consider two cases.

  1. 1.

$|\theta/2|\geq 3^{-k/4}\pi$. Using the bound $|\cos x|\leq 1-(2x/\pi)^{2}$
for $|x|\leq\pi/2$, we have in this case
$|w|=\left|\cos\frac{\theta}{2}\right|\leq 1-4\cdot 3^{-k/2}$, and

$\displaystyle|P(w)|\leq|w|^{n}\cdot 2(n+1)\leq\left(1-4\cdot
3^{-k/2}\right)^{n}\cdot
2(n+1)\leq\exp\left(-\Omega\left(\sqrt{n}\right)\right).$

The last inequality is because $1-x<e^{-x}$ and
$n=\sum_{j=0}^{k}3^{j}<3^{k+1}$.

  2. 2.

$|\theta/2|<3^{-k/4}\pi$. Note that when $j\leq k/4-1$,
$|3^{j}\cdot\frac{\theta}{2}|<\frac{\pi}{3}$. Therefore by item (2) of Lemma
5, we have $|w^{3^{j}}-1|\leq 2\left|\sin\left(3^{j}\theta/4\right)\right|$.
Using the fact that $|\sin x|\leq|x|$, we have

$\displaystyle|R(w)|$
$\displaystyle\leq\prod_{j=0}^{k/4-1}\left|w^{3^{j}}-1\right|\cdot\prod_{j=k/4}^{k}\left|w^{3^{j}}-1\right|\leq\prod_{j=0}^{k/4-1}\left|\frac{3^{j}\theta}{2}\right|\cdot
2^{3k/4}\leq\prod_{j=1}^{k/4}\left(3^{-j}\pi\right)\cdot 2^{3k/4}$
$\displaystyle\leq\exp\left(-\Omega(k^{2})\right)\cdot\exp\left(O(k)\right)=\exp\left(-\Omega(k^{2})\right)=\exp\left(-\Omega\left(\log^{2}n\right)\right).$

Therefore $|P(w)|\leq
2|R(w)|\leq\exp\left(-\Omega\left(\log^{2}n\right)\right)$.

∎

##  5 Higher edit distance with special structures

In this section we show a more general result about strings at higher edit
distance that have a special structure which leads to easy distinguishability.
At the end we also discuss some implications about the edit distance 2 and 4
cases.

We consider pairs of strings
$\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ with the following block
structure:

$\displaystyle\mathbf{x}=\mathbf{x}_{1}\mathbf{x}_{2}\cdots\mathbf{x}_{d},\quad\mathbf{y}=\mathbf{y}_{1}\mathbf{y}_{2}\cdots\mathbf{y}_{d},$

where for each $i=1,2,\ldots,d$, $\mathbf{x}_{i}$ and $\mathbf{y}_{i}$ are
strings of length $\ell_{i}>0$. Moreover, each block $i$ falls into one of the
following cases:

  1. 1.

$\mathbf{x}_{i}=\mathbf{y}_{i}$;

  2. 2.

$\mathbf{x}_{i}=a_{i}\mathbf{s}_{i}$ and $\mathbf{y}_{i}=\mathbf{s}_{i}b_{i}$
for bits $a_{i},b_{i}\in\left\\{0,1\right\\}$ and string $\mathbf{s}_{i}$;

  3. 3.

$\mathbf{x}_{i}=\mathbf{s}_{i}a_{i}$ and $\mathbf{y}_{i}=b_{i}\mathbf{s}_{i}$
for bits $a_{i},b_{i}\in\left\\{0,1\right\\}$ and string $\mathbf{s}_{i}$;

  4. 4.

$\mathbf{x}_{i}=a_{i}\mathbf{s}_{i}$ and $\mathbf{y}_{i}=b_{i}\mathbf{s}_{i}$
for distinct bits $a_{i},b_{i}\in\left\\{0,1\right\\}$ and string
$\mathbf{s}_{i}$;

  5. 5.

$\mathbf{x}_{i}=\mathbf{s}_{i}a_{i}$ and $\mathbf{y}_{i}=\mathbf{s}_{i}b_{i}$
for distinct bits $a_{i},b_{i}\in\left\\{0,1\right\\}$ and string
$\mathbf{s}_{i}$.

We remark that $\mathbf{x}$ and $\mathbf{y}$ of the above form must be within
edit distance $2d$ of each other, yet there are certainly strings of edit
distance $2d$ which fail to follow this pattern (for example
$\mathbf{x}=a_{1}\ldots a_{d}\mathbf{s}$ and $\mathbf{y}=\mathbf{s}b_{1}\ldots
b_{d}$ do not have such block decomposition).

We also note that if $\mathbf{x}$ and $\mathbf{y}$ have different Hamming
weights (the Hamming weight of a string is the number of 1s in it), this makes
them easily distinguishable by a mean-based algorithm. This is because their
traces will exhibit a difference of $q$ in expected Hamming weight. Using only
a constant number of traces, this difference will be noticeable by a mean-
based algorithm. Therefore, we will focus on the more interesting case where
$\mathbf{x}$ and $\mathbf{y}$ have the same Hamming weight.

Under the assumptions above, we prove the following.

######  Theorem 8.

Let $\mathbf{x}$ and $\mathbf{y}$ be strings with the special structure
mentioned above. Then

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B(p;q)\right\\}\geq n^{-O(d^{2})}.$

###### Proof.

As a warm-up, let us first consider the case where all $a_{i}$’s and $b_{i}$’s
are zero. Under this assumption cases 4 and 5 never arise in the above block
decomposition. We can partition $[n]$ into three sets $S_{1},S_{2},S_{3}$,
each of which collecting the indices of contiguous substrings of $\mathbf{x}$
(and therefore of $\mathbf{y}$) of lengths $\ell_{i}$ corresponding to the
respective case of the first three special cases above. Let
$t_{i}=\sum_{j=1}^{i-1}\ell_{j}$ be the starting index of block $i$ (note that
$t_{1}=0$ and $t_{d+1}=n$). As we are going to decompose the polynomials
$Q_{\mathbf{x}}(w)$ and $Q_{\mathbf{y}}(w)$ using the block structure, these
indices will come in handy later.

Recall that the polynomial $Q_{\mathbf{x}}(w)$ is defined as

$\displaystyle
Q_{\mathbf{x}}(w)=x_{0}+x_{1}w+x_{2}w^{2}+\ldots+x_{n-1}w^{n-1}.$

Given the block structure of $\mathbf{x}$ and $\mathbf{y}$, we can express
$Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$ in terms of the polynomials
$Q_{\mathbf{x}_{i}}(w)-Q_{\mathbf{y}_{i}}(w)$ as

$\displaystyle
Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)=\sum_{i=1}^{d}w^{t_{i}}\left(Q_{\mathbf{x}_{i}}(w)-Q_{\mathbf{y}_{i}}(w)\right).$

For $i\in S_{2}$, we have

$\displaystyle
Q_{\mathbf{x}_{i}}(w)-Q_{\mathbf{y}_{i}}(w)=wQ_{\mathbf{s}_{i}}(w)-Q_{\mathbf{s}_{i}}(w)=(w-1)Q_{\mathbf{s}_{i}}(w).$

Similarly for $i\in S_{3}$, we have

$\displaystyle
Q_{\mathbf{x}_{i}}(w)-Q_{\mathbf{y}_{i}}(w)=Q_{\mathbf{s}_{i}}(w)-wQ_{\mathbf{s}_{i}}(w)=(1-w)Q_{\mathbf{s}_{i}}(w).$

Putting everything together, we get

$\displaystyle Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$ $\displaystyle=\sum_{i\in
S_{2}}w^{t_{i}}(w-1)Q_{\mathbf{s}_{i}}(w)+\sum_{i\in
S_{3}}w^{t_{i}}(1-w)Q_{\mathbf{s}_{i}}(w)$
$\displaystyle=(w-1)\left(\sum_{i\in
S_{2}}w^{t_{i}}Q_{\mathbf{s}_{i}}(w)-\sum_{i\in
S_{3}}w^{t_{i}}Q_{\mathbf{s}_{i}}(w)\right).$

Towards applying Lemma 1, we are going to upper bound the number of sign
changes in the second term of the above expression. We note that
$Q_{\mathbf{s}_{i}}(w)$ is a polynomial with 0/1 coefficients. Each summand
$w^{t_{i}}Q_{\mathbf{s}_{i}}(w)$ contains a set of monomials whose degrees are
in an interval $[t_{i},t_{i+1})$, and all these intervals are disjoint from
each other. It follows that the number of sign changes is at most $d$. The
lemma also follows by Theorem 5.

Now let us turn to the case where $a_{i}$’s and $b_{i}$’s are not necessarily
zero. Due to “linearity” of the mapping $\mathbf{x}\mapsto Q_{\mathbf{x}}$
(i.e. $\mathbf{x}+\mathbf{y}\mapsto Q_{\mathbf{x}}+Q_{\mathbf{y}}$), it will
be helpful to write $\mathbf{x}=\mathbf{x}_{\emptyset}+\mathbf{x}_{\Delta}$,
where $\mathbf{x}_{\emptyset}$ is $\mathbf{x}$ but with all the $a_{i}$’s
replaced by zero, and $\mathbf{x}_{\Delta}$ contains only the $a_{i}$’s.
Similarly write $\mathbf{y}=\mathbf{y}_{\emptyset}+\mathbf{y}_{\Delta}$.

We recall that $\mathbf{x}$ and $\mathbf{y}$ have the same Hamming weight.
That means the the following two sets

$\displaystyle A=\left\\{i\colon a_{i}=1\right\\}\textup{ and
}B=\left\\{i\colon b_{i}=1\right\\}$

have the same cardinality. Let $\pi\colon A\rightarrow B$ be a matching
between the $A$ and $B$. For $i\in A$ let $\sigma(i)$ be the index of $a_{i}$
in $\mathbf{x}$ and let $\tau(i)$ be the index of $b_{\pi(i)}$ in
$\mathbf{y}$. It follows that $\sigma(i)=t_{i}$ or $t_{i+1}-1$, and
$\tau(i)=t_{\pi(i)}$ or $t_{\pi(i)+1}-1$, and that

$\displaystyle
Q_{\mathbf{x}_{\Delta}}(w)-Q_{\mathbf{y}_{\Delta}}(w)=\sum_{i\in
A}\left(w^{\sigma(i)}-w^{\tau(i)}\right).$

We then have

$\displaystyle Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$
$\displaystyle=\left(Q_{\mathbf{x}_{\emptyset}}(w)-Q_{\mathbf{y}_{\emptyset}}(w)\right)+\left(Q_{\mathbf{x}_{\Delta}}(w)-Q_{\mathbf{y}_{\Delta}}(w)\right)$
$\displaystyle=\sum_{i\in S_{2}}w^{t_{i}}(w-1)Q_{\mathbf{s}_{i}}(w)+\sum_{i\in
S_{3}}w^{t_{i}}(1-w)Q_{\mathbf{s}_{i}}(w)+\sum_{i\in
A}\left(w^{\sigma(i)}-w^{\tau(i)}\right)$ $\displaystyle=(w-1)\left(\sum_{i\in
S_{2}}w^{t_{i}}Q_{\mathbf{s}_{i}}(w)-\sum_{i\in
S_{3}}w^{t_{i}}Q_{\mathbf{s}_{i}}(w)+\sum_{i\in A}J_{i}(w)\right),$

where each $J_{i}(w)$ is a polynomial of the form

$\displaystyle
J_{i}(w)=\begin{cases}w^{\tau(i)}+w^{\tau(i)+1}+\ldots+w^{\sigma(i)-1}&\textup{if
$\sigma(i)>\tau(i)$},\\\
-w^{\sigma(i)}-w^{\sigma(i)+1}-\ldots-w^{\tau(i)-1}&\textup{if
$\sigma(i)<\tau(i)$}.\end{cases}$

Let us focus on the polynomial $R(w)=R_{1}(w)+R_{2}(w)$ where

$\displaystyle R_{1}(w)\coloneqq\sum_{i\in
S_{2}}w^{t_{i}}Q_{\mathbf{s}_{i}}(w)-\sum_{i\in
S_{3}}w^{t_{i}}Q_{\mathbf{s}_{i}}(w),\quad R_{2}(w)\coloneqq\sum_{i\in
A}J_{i}(w).$

Once more we are going to bound the number of sign changes in $R$. Fix an
arbitrary $i$ and consider two degrees $k_{1}\neq
k_{2}\in[t_{i}+1,t_{i+1}-1)$. From previous discussions we know that
$w^{k_{1}}$ and $w^{k_{2}}$ have the same sign in $R_{1}$. For $R_{2}$, we
note that for each $j\in A$, $w^{k_{1}}$ and $w^{k_{2}}$ have the same
coefficients in $J_{j}$. This is because the coefficients of $J_{j}$ are
identically $1$ (or $-1$) in the degree interval $[\tau(i),\sigma(i))$ (or
$[\sigma(i),\tau(i))$), which either contains or is disjoint with
$\left\\{k_{1},k_{2}\right\\}$. Therefore, the coefficients of $w^{k_{1}}$ and
$w^{k_{2}}$ are the same in $R_{2}$, and hence they have the same sign in
$R=R_{1}+R_{2}$.

Given a sign change $(i,j)$ in $R$ (cf. the remark below Lemma 1), we say an
index $k$ _cuts_ $(i,j)$ if $i\leq k\leq j$. The above argument shows that any
sign change in $R$ must be cut by some index in the set

$\displaystyle
C=\bigcup_{i=1}^{d}\left\\{t_{i},t_{i+1}-1\right\\}=\left\\{t_{1}\right\\}\cup\bigcup_{i=2}^{d}\left\\{t_{i}-1,t_{i}\right\\}\cup\left\\{t_{d+1}-1\right\\}.$

As $t_{1}=0$ and $t_{d+1}-1=n-1$ each cuts at most 1 sign change, and for each
$i$, $t_{i}-1$ and $t_{i}$ jointly cut at most 3 sign changes, it follows that
$R$ has at most $3(d-1)+2=3d-1$ sign changes.

Now we can apply Lemma 1 and get that the multiplicity of zero of
$Q_{\mathbf{x}}-Q_{\mathbf{y}}$ at 1 is at most $3d$ (1 from the factor
$(w-1)$, $3d-1$ from $R(w)$). By Theorem 5, we conclude that

$\displaystyle\sup\left\\{|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)|\colon
w\in\partial B(p;q)\right\\}\geq n^{-O\left((3d)^{2}\right)}=n^{-O(d^{2})}.$

∎

#### What happens to edit distance 2 pairs?

Given that at edit distance 4 there are already hard strings for mean-based
algorithms, this is indeed a natural question to ask. In fact, we will show
that a mean-based algorithm can distinguish between $\mathbf{x}$ and
$\mathbf{y}$ using only polynomially many traces, and this will be an
application of Theorem 8.

######  Corollary 1.

Let $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ be two arbitrary
(distinct) strings with $d_{\textsf{E}}(\mathbf{x},\mathbf{y})=2$. Then
$n^{O(1)}$ traces are sufficient for a mean-based algorithm to distinguish
between $\mathbf{x}$ and $\mathbf{y}$.

###### Proof.

As before we assume $\mathbf{x}$ and $\mathbf{y}$ have the same Hamming
weight. Due to the symmetry between 0 and 1, we may assume without loss of
generality that $\mathbf{x}=\mathbf{a}0\mathbf{b}\mathbf{c}$ and
$\mathbf{y}=\mathbf{a}\mathbf{b}0\mathbf{c}$ for strings
$\mathbf{a},\mathbf{b},\mathbf{c}$ with lengths $a,b,c$, respectively,
satisfying $a+b+c+1=n$. We thus have the block decompositions
$\mathbf{x}=\mathbf{x}_{1}\mathbf{x}_{2}\mathbf{x}_{3}$ and
$\mathbf{y}=\mathbf{y}_{1}\mathbf{y}_{2}\mathbf{y}_{3}$ where

$\mathbf{x}_{1}=\mathbf{a}$, |  $\mathbf{x}_{2}=\mathbf{b}0$, |  $\mathbf{x}_{3}=\mathbf{c}$,
---|---|---
$\mathbf{y}_{1}=\mathbf{a}$, |  $\mathbf{y}_{2}=0\mathbf{b}$, |  $\mathbf{y}_{3}=\mathbf{c}$.

Note that this falls into the special strucutre mentioned above for $d=3$.
Theorem 8 then implies

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B(p;q)\right\\}\geq n^{-O(1)},$

from which it follows that $n^{O(1)}$ traces are sufficient to distinguish
between $\mathbf{x}$ and $\mathbf{y}$. ∎

In fact, with a more careful analysis one can nail down the constant and show
that the sample complexity is $O(n^{2})$, leading to a sharp transition in
sample complexity from edit distance 2 to 4.

#### Other cases for edit distance 4

We also mention that the only hard pairs at edit distance 4 have the form

$\displaystyle\mathbf{x}$ $\displaystyle=\mathbf{a}\ a_{1}\ \mathbf{b}\ a_{2}\
\mathbf{c}\ \mathbf{d}\ \mathbf{e},$ $\displaystyle\mathbf{y}$
$\displaystyle=\mathbf{a}\ \mathbf{b}\ \mathbf{c}\ b_{1}\ \mathbf{d}\ b_{2}\
\mathbf{e}.$

The hard strings given in Theorem 2 are also in this form with
$\mathbf{b}=\mathbf{d}=\varepsilon$ (the empty string). All other pairs not in
this form will have the special structure mentioned earlier, and are thus
easy.

##  6 Conclusions and Open Problems

In this work we showed several results about the power and limitation of mean-
based algorithms in distinguishing trace distributions of strings at small
Hamming or edit distance.

Many open questions remain, besides whether the worst-case reconstruction
problem is solvable in polynomial time. We state below a few questions
stemming from our work here.

Problem 1 Can the connection between the multiplicity of zero at 1 and the
supremum over the circle $\partial B(p;q)$ be tightened? Specifically, is the
bound in Theorem 5 tight?

Problem 2 Is the converse of Theorem 5 true? Namely, does high multiplicity of
zero at $1$ necessarily imply a small supremum over $\partial B(p;q)$? An
affirmative answer to this question would establish an equivalence between PTE
solutions and hard instances against mean-based trace reconstruction.

##  7 Acknowledgements

We are indebted to some anonymous reviewers for pointing us to several
references that we previously missed and for many useful suggestions that have
been incorporated in the current writeup.

## References

  * [BCF+19] Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, and Sandip Sinha.  Beyond trace reconstruction: Population recovery from the deletion channel.  CoRR, abs/1904.05532, 2019.
  * [BE97] Peter Borwein and Tamás Erdélyi.  Littlewood-type problems on subarcs of the unit circle.  Indiana University mathematics journal, pages 1323–1346, 1997.
  * [BEK99] Peter Borwein, Tamás Erdélyi, and Géza Kós.  Littlewood-type problems on [0, 1].  Proceedings of the London Mathematical Society, 79(1):22–46, 1999\.
  * [BI94] P. Borwein and C. Ingalls.  The Prouhet-Tarry-Escott problem revisited.  Enseign. Math, 40:3–27, 1994.
  * [BKKM04] Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor.  Reconstructing strings from random traces.  In J. Ian Munro, editor, SODA, pages 910–918. SIAM, 2004.
  * [BLS20] Joshua Brakensiek, Ray Li, and Bruce Spang.  Coded trace reconstruction in a constant number of traces.  page (to appear), 2020.
  * [CDL+20] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the smoothed complexity model, 2020.
  * [Cha19] Zachary Chase.  New lower bounds for trace reconstruction.  arXiv preprint arXiv:1905.03031, 2019.
  * [Cha20] Zachary Chase.  New upper bounds for trace reconstruction, 2020.
  * [CRGM19] Mahdi Cheraghchi, João L. Ribeiro, Ryan Gabrys, and Olgica Milenkovic.  Coded trace reconstruction.  In ITW, pages 1–5. IEEE, 2019.
  * [Des86] René Descartes.  La géométrie.  Hermann, 1886.
  * [Dic13] Leonard Eugene Dickson.  History of the Theory of Numbers, Volume II: Diophantine Analysis, volume 2.  Courier Corporation, 2013.
  * [DOS17] Anindya De, Ryan O’Donnell, and Rocco A Servedio.  Optimal mean-based algorithms for trace reconstruction.  In STOC, pages 1047–1056, 2017.
  * [Erd14] Tamás Erdélyi.  Coppersmith-rivlin type inequalities and the order of vanishing of polynomials at 1.  arXiv preprint arXiv:1406.2560, 2014.
  * [Erd19] Tamás Erdélyi.  On the multiplicity of the zeros of polynomials with constrained coefficients.  2019\.
  * [ES59] P Erdos and G Szekeres.  On the product n k= 1 (1- zak), acad.  Serbe Sci. Publ. Inst. Math, 13:29–34, 1959.
  * [GM17] Ryan Gabrys and Olgica Milenkovic.  The hybrid k-deck problem: Reconstructing sequences from short and long traces.  In ISIT, pages 1306–1310. IEEE, 2017.
  * [GM19] Ryan Gabrys and Olgica Milenkovic.  Unique reconstruction of coded strings from multiset substring spectra.  IEEE Trans. Inf. Theory, 65(12):7682–7696, 2019.
  * [HHP18] Lisa Hartung, Nina Holden, and Yuval Peres.  Trace reconstruction with varying deletion probabilities.  In ANALCO, pages 54–61. SIAM, 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 SODA, pages 389–398. SIAM, 2008.
  * [HPP18] Nina Holden, Robin Pemantle, and Yuval Peres.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  In COLT, volume 75, pages 1799–1840, 2018.
  * [Hua82] Loo Keng Hua.  Introduction to number theory.  Springer, 1982.
  * [KM05] Sampath Kannan and Andrew McGregor.  More on reconstructing strings from random traces: insertions and deletions.  In ISIT, pages 297–301. IEEE, 2005.
  * [KMMP19] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal.  Trace reconstruction: Generalized and parameterized.  In ESA, volume 144, pages 68:1–68:25, 2019.
  * [KR97] Ilia Krasikov and Yehuda Roditty.  On a reconstruction problem for sequences,.  J. Comb. Theory, Ser. A, 77(2):344–348, 1997.
  * [Lan13] Serge Lang.  Complex analysis, volume 103.  Springer Science & Business Media, 2013.
  * [Lev01a] Vladimir I. Levenshtein.  Efficient reconstruction of sequences.  IEEE Trans. Inf. Theory, 47(1):2–22, 2001.
  * [Lev01b] Vladimir I. Levenshtein.  Efficient reconstruction of sequences from their subsequences or supersequences.  J. Comb. Theory, Ser. A, 93(2):310–332, 2001.
  * [MPV14] Andrew McGregor, Eric Price, and Sofya Vorotnikova.  Trace reconstruction revisited.  In ESA, volume 8737 of Lecture Notes in Computer Science, pages 689–700. Springer, 2014.
  * [NP17] Fedor Nazarov and Yuval Peres.  Trace reconstruction with $\exp(O(n^{1/3}))$ samples.  In STOC, pages 1042–1046, 2017.
  * [NR20] Shyam Narayanan and Michael Ren.  Circular trace reconstruction, 2020.
  * [Pro51] Eugéne Prouhet.  Mémoire sur quelques relations entre les puissances des nombres.  CR Acad. Sci. Paris, 33(225):1851, 1851.
  * [PS97] George Pólya and Gabor Szegö.  Problems and Theorems in Analysis II: Theory of Functions. Zeros. Polynomials. Determinants. Number Theory. Geometry.  Springer Science & Business Media, 1997.
  * [PZ17] Yuval Peres and Alex Zhai.  Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice.  In FOCS, pages 228–239. IEEE Computer Society, 2017.
  * [Sco97] Alex D Scott.  Reconstructing sequences.  Discrete Mathematics, 175(1-3):231–238, 1997.
  * [VS08] Krishnamurthy Viswanathan and Ram Swaminathan.  Improved string reconstruction over insertion-deletion channels.  In SODA, page 399–408. Society for Industrial and Applied Mathematics, 2008.
  * [Wri35] E. M. Wright.  On Tarry’s problem (I).  The Quarterly Journal of Mathematics, (1):261–267, 1935.
  * [Wri59] E. M. Wright.  Prouhet’s 1851 solution of the Tarry-Escott problem of 1910.  The American Mathematical Monthly, 66(3):199–201, 1959.

##  Appendix A Mean-based algorithms and connection to complex analysis

Fix a string $\mathbf{x}\in\left\\{0,1\right\\}^{n}$. The basic idea of
[DOS17] and [NP17] is to consider the average number of “1”s at index $j$ in
the traces of $\mathbf{x}$, i.e. the expectations
$E_{j}(\mathbf{x})\coloneqq\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}[\tilde{x}_{j}]$
for $j=0,2,\ldots,n-1$, where $\tilde{x}_{j}=0$ for
$j>|\tilde{\mathbf{x}}|-1$. An algorithm is said to be _mean-based_ if its
output depends only on the statistical estimates of $E_{j}(\mathbf{x})$ where
$j=0,1,\ldots,n-1$.

###  A.1 The reduction to complex analysis

[DOS17] and [NP17] showed the following bound.

######  Theorem 9 ([DOS17], [NP17]).

For all distinct $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ it is the
case that

$\displaystyle\quad\sum_{j=0}^{n-1}\left|E_{j}(\mathbf{x})-E_{j}(\mathbf{y})\right|>\exp\left(-O\left(n^{1/3}\right)\right).$
(1)

This result is sufficient to imply that $\exp\left(O(n^{1/3})\right)$ samples
can tell the difference between $\mathcal{D}_{\mathbf{x}}$ and
$\mathcal{D}_{\mathbf{y}}$ with high probability. To this end, they defined
the following polynomial

$\displaystyle P_{\mathbf{x}}(z)=\sum_{j=0}^{n-1}E_{j}(\mathbf{x})\cdot
z^{j}.$

This makes the left-hand-side of (1) simply $\left\lVert
P_{\mathbf{x}}-P_{\mathbf{y}}\right\rVert_{1}$. By writing explicitly

$\displaystyle
E_{j}(\mathbf{x})=\sum_{k=0}^{n-1}\Pr\left[\tilde{x}_{j}\textup{ comes from
}x_{k}\right]\cdot x_{k}=\sum_{k=0}^{n-1}\binom{k}{j}p^{k-j}q^{j+1}\cdot
x_{k},$

we have that

$\displaystyle P_{\mathbf{x}}(z)$
$\displaystyle=\sum_{j=0}^{n-1}E_{j}(\mathbf{x})\cdot
z^{j}=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}\binom{k}{j}p^{k-j}q^{j+1}\cdot
x_{k}\cdot z^{j}$
$\displaystyle=q\sum_{k=0}^{n-1}x_{k}\sum_{j=0}^{n-1}\binom{k}{j}p^{k-j}(qz)^{j}$
$\displaystyle=q\sum_{k=0}^{n-1}x_{k}\cdot\left(p+qz\right)^{k}$
$\displaystyle=q\cdot Q_{\mathbf{x}}(p+qz).$

In light of Lemma 2, one might as well bound $\left\lVert
P_{\mathbf{x}}-P_{\mathbf{y}}\right\rVert_{\infty}$. Keeping in mind that the
map $z\mapsto p+qz$ shifts the complex unit circle $\partial B(0;1)$ to
$\partial B\left(p;q\right)$, so far we have reduced the problem to
understanding the following supremum

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B\left(p;q\right)\right\\}.$

Using a result of [BE97], [DOS17] and [NP17] proved that the above supremum is
at least $\exp\left(-O(n^{1/3})\right)$, which is their main technical result.

To summarize, we have the following generic lemma.

######  Lemma 6.

Let $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ be two strings. Then

$\displaystyle\frac{1}{\sqrt{n+1}}\left\lVert
P_{\mathbf{x}}-P_{\mathbf{y}}\right\rVert_{1}\leq
q\cdot\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B\left(p;q\right)\right\\}\leq\left\lVert
P_{\mathbf{x}}-P_{\mathbf{y}}\right\rVert_{1}.$

###### Proof.

We have that $q^{-1}P_{\mathbf{x}}(z)=Q_{\mathbf{x}}(w)$ where $w=p+qz$.
Applying Lemma 2 to the polynomial
$q^{-1}\left(P_{\mathbf{x}}-P_{\mathbf{y}}\right)$ gives the lemma. ∎

A common bound in this paper is of the form

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B\left(p;q\right)\right\\}\geq n^{-O(d)}$

for some parameter $d$. A standard Chernoff-Hoeffding bound argument shows
that $n^{O(d)}$ traces are sufficient for a mean-based algorithm to
distinguish between $\mathbf{x}$ and $\mathbf{y}$. For a formal discussion
about the sample complexity versus various notions of distances related to the
trace problem we refer the reader to [HL20].

##  Appendix B Distinguishing between strings within small Hamming distance

We prove Theorem 1 in this section.

###  B.1 A weak bound using Theorem 5

We first show that how to apply the multiplicity argument to get a worse bound
$n^{O(d^{2})}$. This will be an immediate consequence of Descartes’ rule of
sign changes.

######  Corollary 2.

Let $\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ be such that
$d_{\textsf{H}}(\mathbf{x},\mathbf{y})\leq d$. Then

$\displaystyle\sup\left\\{\left|Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)\right|\colon
w\in\partial B(p;q)\right\\}\geq n^{-O(d^{2})}.$

###### Proof.

Let $Q(w)=Q_{\mathbf{x}}(w)-Q_{\mathbf{y}}(w)$. We will show that the
multiplicity of zero of $Q$ at 1 is at most $d$.

We note that $Q(w)$ is a polynomial with at most $d$ non-zero terms. Therefore
the number of sign changes $C(Q)$ can never exceed $d$. By Lemma 1, the number
of real positive roots of $Q$ is at most $d$. In particular, the multiplicity
of zero of $Q$ at 1 is at most $d$. Thus the $n^{-O(d^{2})}$ bound follows
from Lemma 1 and Theorem 5. ∎

The sample complexity bound $n^{O(d^{2})}$ follows from the above corollary.

###  B.2 Proof of Theorem 1

We now perform a more careful analysis to obtain the $n^{O(d)}$ bound in
Theorem 1. We remark that the same result was proven in [KMMP19], which uses a
previous result regarding reconstructing strings from their “$k$-decks” (i.e.
the multi-set of subsequences of length $k$)[KR97]. One of the results in
[KR97] states that strings within Hamming distance $2k$ have different
$k$-decks. Therefore when the deletion probability $p\leq 1-k/n$, the traces
will have length at least $k$ in expectation and we can reconstruct the
$k$-deck with high probability in $n^{O(k)}$ traces. This is exactly the
argument in [KMMP19], but we note here that this argument does not yield a
mean-based algorithm.

We are going to present a proof based on potential functions. Given a trace
$\tilde{\mathbf{x}}\in\left\\{0,1\right\\}^{\leq n}$, define the following
potential functions for integers $k\geq 0$:

$\displaystyle\Phi_{k}(\tilde{\mathbf{x}})=\sum_{i=0}^{n-1}\binom{i}{k}\tilde{x}_{i}.$

Similar potential functions were considered in [Sco97] in the context of
reconstructing strings from $k$-decks. Due to the slight difference in the
problem settings, we include the proofs here.

We recall that $\tilde{x}_{i}=0$ whenever $i>|\tilde{\mathbf{x}}|-1$. Note its
expectation
$\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}[\Phi_{k}(\tilde{\mathbf{x}})]$
is a fixed value which depends only $\mathbf{x}$, and can be estimated by a
mean-based algorithm. We are going to use the following simple bound
$\binom{i}{k}\leq n^{k}$ for all $0\leq i\leq n-1$. The following lemma will
directly imply Theorem 1.

######  Lemma 7.

For any two distinct strings
$\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ with
$d_{\textsf{H}}(\mathbf{x},\mathbf{y})\leq d$, there exists $0\leq k\leq d-1$
such that

$\displaystyle\left|\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}\left[\Phi_{k}(\tilde{\mathbf{x}})\right]-\mathop{\mathbb{E}}_{\tilde{\mathbf{y}}\sim\mathcal{D}_{\mathbf{y}}}\left[\Phi_{k}(\tilde{\mathbf{y}})\right]\right|\geq
q^{k+1}\geq q^{d}.$

###### Proof.

Calculation yields the following expression for the expectation

$\displaystyle\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}\left[\Phi_{k}(\tilde{\mathbf{x}})\right]$
$\displaystyle=\sum_{i=0}^{n-1}\binom{i}{k}\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}[\tilde{x}_{i}]=\sum_{i=0}^{n-1}\binom{i}{k}\sum_{j=0}^{n-1}x_{j}\cdot\Pr\left[\tilde{x}_{i}\textup{
comes from }x_{j}\right]$
$\displaystyle=\sum_{i=0}^{n-1}\binom{i}{k}\sum_{j=0}^{n-1}x_{j}\cdot\binom{j}{i}p^{j-i}q^{i+1}$
$\displaystyle=q\sum_{j=0}^{n-1}x_{j}\sum_{i=0}^{n-1}\binom{i}{k}\binom{j}{i}p^{j-i}q^{i}$
$\displaystyle=q^{k+1}\sum_{j=0}^{n-1}x_{j}\sum_{i=0}^{n-1}\binom{j}{k}\binom{j-k}{i-k}p^{j-i}q^{i-k}$
$\displaystyle=q^{k+1}\sum_{j=0}^{n-1}\binom{j}{k}x_{j}.$

Here the second last equality is due to the identity
$\binom{i}{k}\binom{j}{i}=\binom{j}{k}\binom{j-k}{i-k}$. Denote
$\Delta=\left\\{i\colon x_{i}\neq y_{i}\right\\}$ as the set of indices at
which $\mathbf{x}$ and $\mathbf{y}$ differ, which has size $|\Delta|=d$ by
assumption. We thus have

$\displaystyle\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}\left[\Phi_{k}(\tilde{\mathbf{x}})\right]-\mathop{\mathbb{E}}_{\tilde{\mathbf{y}}\sim\mathcal{D}_{\mathbf{y}}}\left[\Phi_{k}(\tilde{\mathbf{y}})\right]=q^{k+1}\sum_{j\in\Delta}\binom{j}{k}\cdot\varepsilon_{j},$

where $\varepsilon_{j}=x_{j}-y_{j}\in\left\\{-1,1\right\\}$ for $j\in\Delta$.
Let $j_{1}<j_{2}<\cdots<j_{d}$ be the elements of $\Delta$ and consider the
system of linear equations defined by the following $d\times d$ matrix

$\displaystyle\mathbf{A}=\begin{bmatrix}\binom{j_{1}}{0}&\binom{j_{2}}{0}&\cdots&\binom{j_{d}}{0}\\\
\binom{j_{1}}{1}&\binom{j_{2}}{1}&\cdots&\binom{j_{d}}{1}\\\
\vdots&\vdots&\ddots&\vdots\\\
\binom{j_{1}}{d-1}&\binom{j_{2}}{d-1}&\cdots&\binom{j_{d}}{d-1}\end{bmatrix}.$

Since the polynomials $p_{j}(z)=\binom{z}{j}$ ($j=0,1,\dots,d-1$) form a basis
for the space of polynomials of degree at most $d-1$, we can see that
$\mathbf{A}$ has the same rank as the Vandermonde matrix generated by
$\left\\{j_{1},\ldots,j_{d}\right\\}$. In particular, $\mathbf{A}$ has a
trivial kernel since the $j_{i}$’s are distinct. That implies for every
$\left(\varepsilon_{j_{1}},\ldots,\varepsilon_{j_{d}}\right)\neq\mathbf{0}$,
there exists a row $1\leq k\leq d$ for which
$\sum_{j\in\Delta}\binom{j}{k}\cdot\varepsilon_{j}\neq 0$. As every term in
this sum is an integer, we conclude that

$\displaystyle\left|\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}\left[\Phi_{k}(\tilde{\mathbf{x}})\right]-\mathop{\mathbb{E}}_{\tilde{\mathbf{y}}\sim\mathcal{D}_{\mathbf{y}}}\left[\Phi_{k}(\tilde{\mathbf{y}})\right]\right|=q^{k+1}\left|\sum_{j\in\Delta}\binom{j}{k}\cdot\varepsilon_{j}\right|\geq
q^{k+1}.$

as desired. ∎

###### Proof of Theorem 1.

Suppose we want to distinguish between $\mathbf{x}$ and $\mathbf{y}$ where
$d_{\textsf{H}}(\mathbf{x},\mathbf{y})\leq d$. Set $T=10(n/q)^{2(d+2)}$ to be
the number of traces and let $k$ be the index suggested by Lemma 7. Given the
traces
$\tilde{\mathbf{x}}^{(1)},\tilde{\mathbf{x}}^{(2)},\ldots,\tilde{\mathbf{x}}^{(T)}$,
the mean-based algorithm has access to the following estimates

$\displaystyle\tilde{E}_{j}=\frac{1}{T}\sum_{t=1}^{T}\tilde{x}^{(t)}_{j},\quad
j=0,1,\ldots,n-1.$

These estimates are used to approximate the potential function as
$\tilde{\Phi}_{k}=\sum_{j=0}^{n-1}\binom{j}{k}\tilde{E}_{j}$. Finally, the
algorithm outputs $\mathbf{x}$ if $\tilde{\Phi}_{k}$ is closer to
$\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}[\Phi_{k}(\tilde{\mathbf{x}})]$
than to
$\mathop{\mathbb{E}}_{\tilde{\mathbf{y}}\sim\mathcal{D}_{\mathbf{y}}}[\Phi_{k}(\tilde{\mathbf{y}})]$,
and outputs $\mathbf{y}$ otherwise.

We may assume $\mathbf{x}$ is the correct string. By the Chernoff-Hoeffding
bound and a union bound, with high probability the following event occurs:

$\displaystyle\forall
j=0,1,\ldots,n-1,\quad\left|\tilde{E}_{j}-E_{j}(\mathbf{x})\right|<\frac{1}{2}\left(\frac{q}{n}\right)^{d+1}.$

Conditioned on this event, we have

$\displaystyle\left|\tilde{\Phi}_{k}-\mathop{\mathbb{E}}_{\tilde{\mathbf{x}}\sim\mathcal{D}_{\mathbf{x}}}[\Phi_{k}(\tilde{\mathbf{x}})]\right|\leq\sum_{j=0}^{n-1}\binom{j}{k}\left|\tilde{E}_{k}-E_{k}(\mathbf{x})\right|<n^{d}\cdot
n\cdot\frac{1}{2}\left(\frac{q}{n}\right)^{d+1}<\frac{q^{d}}{2}.$

According to Lemma 7, the algorithm will output the correct answer
$\mathbf{x}$. ∎