A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence $s \in \{0,1\}^{\leq n}$, and one chooses a set of queries $y \in \{0,1\}^{\mc{O}(n)}$ and receives $d(s,y)$ for a distance function $d$. The goal is to make as few queries as possible to recover $s$. Although this problem is well-studied for decomposable distances, i.e., distances of the form $d(s,y) = \sum_{i=1}^n f(s_i, y_i)$ for some function $f$, which includes the important cases of Hamming distance, $\ell_p$-norms, and $M$-estimators, to the best of our knowledge this problem has not been studied for non-decomposable distances, for which there are important special cases such as edit distance, dynamic time warping (DTW), distance, earth mover's distance, and so on. We initiate the study and develop a general framework for such distances. Interestingly, for some distances such as DTW or , exact recovery of the sequence $s$ is provably impossible, and so we show by allowing the characters in $y$ to be drawn from a slightly larger alphabet this then becomes possible. In a number of cases we obtain optimal or near-optimal query complexity. We also study the role of adaptivity for a number of different distance functions.  One motivation for understanding non-adaptivity is that the query sequence can be fixed and the distances of the input to the queries provide a non-linear embedding of the input, which can be used in downstream applications involving, e.g., neural networks for natural language processing.

§ INTRODUCTION

We study the problem of exact recovery of a sequence from queries to a distance oracle.
We study the problem of exact recovery of a sequence from queries to a distance oracle.
Suppose there is an unknown input sequence $s$ with length at most $n$, defined on a binary alphabet $\{0,1\}$.
Assume we have a distance oracle which returns the distance $d(s,q)$ between a query sequence $q$ and the unknown sequence $s$, where the query sequence $q$ is chosen either adaptively or non-adaptively.
The problem is to determine the sequence $s$ with a minimal number of queries to the distance oracle.
This problem has been studied for decomposable distances, that is, the distance function between two sequences can be computed as the sum of distances between pairs of characters at the same entry, but never for non-decomposable distances.
Among all non-decomposable distances, we are particularly interested in the edit distance, ($p$)-Dynamic Time Warping ($p$-DTW), and distances.
The edit distance measures the minimum number of edit operations (i.e., insertions, deletions, and substitutions) for transforming one sequence to another.
intro-dtwThe $p$-DTW distance ($1\le p<\infty$) between two sequences $x, y$ is defined as the minimum $\ell_p$ distance between two equal-length expansions of $x, y$, where the expansion of a sequence means you can duplicate each character of each sequence an arbitrary number of times.
When $p=1$, the $p$-DTW distance is called the DTW distance.
If we consider the $\ell_\infty$ norm instead of the $\ell_p$ norm, we obtain the distance.

The problem of exact recovery for decomposable distances is well-studied in the literature, under the names of the coin-weighing problem [Shapiro and Fine, 1960, Bshouty, 2009] and the group testing problems [Dorfman, 1943, Aldridge et al., 2019, Coja-Oghlan et al., 2020].
The coin-weighing problem is to identify the weight of each coin from a collection of $n$ coins, each being of weight either $w_0$ or $w_1$ ($w_0$ and $w_1$ are distinct). In this problem, our only access to the coins is via weighing a subset of the coins on a spring scale.
The group testing problem has also been shown to be equivalent to the coin-weighing problem in some settings  [Wang et al., 2018].
This line of research has been extensively studied with interesting applications.
For example, the coin-weighing problem can be found in the detection problem [Soderberg and Shapiro, 1963], the problem of determining a collection [Cantor and Mills, 1966], and the distinguishing family problem [Li and Vitányi, 1991].

The query complexity of the adaptive version of the problem is also related to the original Mastermind game [Knuth, 1976].
The Mastermind problem can be phrased as guessing an input sequence based on Hamming distance queries.
The non-adaptive version of this problem can be shown to be equivalent to the well-studied non-adaptive coin-weighing problem [Bshouty, 2009].
One can then consider other variants of the Mastermind game where the input sequence is guessed based on other distance metrics, such as permutation-based distances [Afshani et al., 2019], $\ell_p$ distances [Fernandez et al., 2019] and graph distances [Rodríguez-Velázquez et al., 2014, Jiang and Polyanskii, 2019].
However, general distance metrics that do not decompose into coordinate sums are less understood.
In this paper, we initiate the study of this exact recovery problem on  non-decomposable distances.

One motivation of our exact recovery problem is its application to adversarially robust learning on  discrete domains.
It is well-known that deep neural networks are vulnerable to adversarial examples: test inputs that have been modified slightly in the $\ell_p$ space can lead to problematic machine predictions.
Though there exist various techniques such as Pixel-DP [Lécuyer et al., 2019] and randomized smoothing [Cohen et al., 2019] that achieve certified robustness against $\ell_p$-norm perturbations in continuous domains, in many tasks such as natural language processing, the $\ell_p$ norm is not well-defined for discrete perturbations.
To resolve this issue, inputs from a discrete domain are usually mapped to vectors in the $\ell_p$ space before being passed to a classifier; this is also known as a word embedding.
We require two properties of such a mapping: 1) zero information loss; 2) Lipschitzness with respect to the distance metric in the input space.
We show that the exact recovery problem yields a direct construction of such mappings: suppose the set of query sequences is $\{q_1, \ldots, q_m\}$ and $s$ is the unknown input sequence; the mapping for $s$: $\phi{(s)} = [d(s, q_1), \ldots, d(s, q_m)]$ has Lipschitz constant at most $\sqrt{m}$ (in the $\ell_2$ norm) and maintains complete information about $s$.
Similar to edit distance, which can be used for describing the adversarial capability in changing sequences, the DTW and distances have received significant attention for their flexibility in handling temporal sequences.
The special instance of our problem on DTW and distances may be useful for analyzing the robustness of DTW neural networks [Cai et al., 2019].

A distance embedding further inspires theoretical applications in functional analysis [Vershynin, 2011]. While the space of input sequence $s$ is a metric space, it may not be a Hilbert space with a definition of norm and inner product. Our result provides us with a tool to define a mapping from a metric space to a Hilbert space without loss of information about the input sequences. One can then use the norm or inner product to analyze input sequences, e.g., when two input sequences are orthogonal and how to normalize an input sequence to have norm $1$.

§.§ Our Assumptions

I don't think this section says much. How about deleting it?
We start from clarifying the assumptions made in this paper.
Throughout the paper, we assume the alphabet of the unknown input sequence $s$ is .
To recover this sequence, we submit adaptive or non-adaptive query sequences to the distance oracles where these query sequences may be allowed to utilize alphabets outside .
We assume the maximum length of $s$ is $n$ while the exact length of $s$ is unknown.
In the solution to our problems, we introduce one additional character in the query sequence to edit distance and $\mathcal{O}(n)$ additional characters in the query sequence to the DTW distance This is not true.
For edit distance, introducing more than 1 extra characters cannot encode more information in the query results, because the edit distance between 0 (or 1) and any other additional character is the same edit distance between two characters?.

§.§ Our Contribution and Results

To the best of our knowledge, this paper makes the first effort to consider the non-decomposable distance recovery problem.
We first present a general framework to tackle with this problem, and then exhaustively explore representative distances of this class, i.e., edit distance, DTW distance, and distance.
We also study the role of adaptivity and non-adaptivity and obtain a number of results on lower bounds and upper bounds of query complexity.
Before introducing our technical results, we would like to clarify the assumptions we make in the setting of the problem and justify some of them.

Throughout the paper, we assume the alphabet of the unknown input sequence $s$ is . We note that under this assumption, all of our results for DTW described below will apply to $p$-DTW.
To recover the sequence $s$, we submit adaptive or non-adaptive query sequences to a distance oracle. As we will show in Section <ref>, for some distance metrics, there exist input sequences that cannot be distinguished by any sequence on a binary alphabet. Therefore, our query sequences may be allowed to utilize alphabets outside with $\mc{O}(1)$ extra characters to exactly recover the input sequence.
For edit distance, the extended alphabet can contain any symbol outside the binary alphabet, as the edit distance oracle counts the edit operations no matter what symbol is used.
For ($p$-)DTW distance and distance, the extended alphabet can consist of any real number.
We assume the maximum length of $s$ is $n$, while the exact length of $s$ is unknown.

Extension to non-binary inputs.

The binary input sequence setting is not an over-simplified assumption.
All the results we obtain on the binary setting can be naturally extended to any non-binary alphabet $\Sigma$ by encoding the non-binary alphabet in a binary domain.
This will increase the query complexity by a constant factor from $|\Sigma|$ (one-hot encoding) to $\log(|\Sigma|)$ (binary encoding).
Though this may not be the best solution if one considers a large alphabet, this extension works for the results for all distance metrics shown in this paper.
Improvement on this extension to the recovery problem leaves room for future research.

optimalityThroughout the paper, we consider asymptotic optimality, that is, the asymptotic complexity lower and upper bounds match orderwise.
We would like to investigate lower bounds of the problem per distance instance, and develop algorithms that shows upper bounds can match lower bounds up to constant factor or logarithmic factor (under Big-O / Big-Omega tilde notation).

To list the results we obtain on this non-decomposable distance recovery problem,
we begin with a general coordinate descent framework that can help recover sequences from a large class of distance oracles, including but not limited to earth mover's distance (EMD), cascaded norms ($\ell_p$ of $\ell_q$), and $A$ norms (a.k.a. Mahalanobis distance).
We then present improved results on three specific distance metrics: edit distance, DTW distance, and distance. We first provide several observations on the sequence recovery problem, showing the existence of indistinguishable input sequences despite the fact that we can query their DTW and Fréchet distances with all possible binary query sequences.
We also prove lower bounds on the query complexity in our distance recovery problem w.r.t. DTW, edit, and distances.
Then we present our main results on recovering sequences from edit, DTW, and distance oracles, with adaptive and non-adaptive strategies.

§.§.§ Existence of Indistinguishable Sequences

We observe that, for some distances, there exist sequences that cannot be distinguished by any query sequence over a binary alphabet.
This can be proved by showing concrete examples, i.e., a pair of sequences that cannot be distinguished, which we show is true for the DTW and the distances, as stated in the following theorem.

There exists a pair of sequences $(s, s')$ such that $s$ and $s'$ cannot be distinguished by any query sequence on a binary alphabet, for the DTW distance and the distance.

The formal proof of this theorem for the DTW distance is deferred to Theorem <ref>.
The analogous discussion for the distance can be found in Section <ref>.
Due to the existence of indistinguishable sequences, we define the concept of an equivalence class of sequences, which is a set of input sequences which are indistinguishable from all queries by a given distance oracle.

This observation suggests the scope of the distance recovery problem we study.
We further categorize the recovery guarantee into the following three levels, from strong to weak:
1) recover the exact input sequence;
2) recover any sequence in the same equivalent class of the input sequence, where the equivalence class is defined to be the set for which any two input sequences in the equivalence class cannot be distinguished by calling the distance oracle to all query sequences;
3) recover any sequence which has zero distance to the input sequence.
While the third level is the weakest one, in certain cases it can be reduced to the first two levels—for norm-induced distance functions, the recovered sequence is exactly the input sequence; for semi-norm-induced distance functions, the recovered sequence is in the same equivalence class.
For other distance functions which are not metric, recovering a sequence with zero distance to input does not necessarily imply any one of the first two levels.
We will show that our general coordinate descent framework can recover sequences with the third-level guarantee.

§.§.§ General Coordinate Descent Framework for Adaptively Querying Distance Oracles

We develop a general framework for recovering an input sequence from adaptive queries, which models the problem as a zero-th order optimization and utilizes a coordinate-descent-based algorithm to give a solution.
The coordinate descent framework defines the distance between the input sequence and the query sequence as the loss function. The objective of the optimization is to reduce the loss function to $0$, which guarantees what we call the third level of recovery.
We define a step operation to modify the query sequence. For example, in the context of edit distance, a step operation is defined as adding/removing/substituting a character of the query sequence.
To perform coordinate descent, our algorithm performs one step operation each time and queries the oracle to find a direction for which the loss decreases by at least a pre-determined constant scalar.
By iteratively performing this method, the loss can be reduced to $0$ and we show that the overall complexity of this method is $\poly(n)$, given that the maximum length of the sequence is $n$.
For a large class of non-decomposable distance functions, such as the earth mover's distance (EMD), the cascaded norm ($\ell_p$ of $\ell_q$), and the $A$ norm, we can use this framework to yield a solution, as stated in the following theorem.

For an arbitrary distance oracle, a binary alphabet $\bits$ and any input sequence $s \in \bits^i$ where $0 \leq i \leq n$, using coordinate descent can reduce the distance to the input sequence $s$ to 0, by adaptively querying the distance oracle between $s$ and a set of query sequences with query complexity at most $\poly(n)$.

Sufficient conditions for using this framework and further details can be found in Theorem <ref>.

§.§.§ Lower Bounds on the Recovery Problem

If we study the problem of exact recovery (the first level of recovery), we can obtain an information-theoretic lower bound of  $\Tilde{\Omega}(n)$ for various distance oracles, given by the following theorem.
Here $f(n) = \Tilde{\Omega}(g(n))$ if poly-1$f(n) = \Omega(g(n)/\polylog(n))$.

For any input sequence $s \in \bits^i$ where $0 \leq i \leq n$, if for any input sequence and query the distance oracle has $\poly(n)$ possible values, any algorithm which exactly recovers $s$ by querying the distance oracle between $s$ and a set of query sequences requires query complexity at least $\Tilde{\Omega}(n)$.

The idea behind this bound is that, there are exponentially many possible input sequences with length at most $n$, while for the distance oracles given in our setting, the output of each query is a distance between two sequences which only has $\poly(n)$ possibilities. Hence, we need at least
We instantiate this theorem on the edit distance and DTW distance in Theorem <ref> and Theorem <ref>, for recovery to the exact input distance.

We note for the DTW distance and distance, there exist indistinguishable sequences, which lead to the recovery problem for equivalence class.
Since the total number of equivalence classes is less than the number of input sequences, the previous counting technique (based on simple facts from information theory) no longer works. So we need a different argument, as we give in the following theorem:

Summary of our results for recovering arbitrary input sequences of length $n$ under the constraint that the query length is of $\mc{O}(n)$. LB: Lower Bound. #EC: Number of Extra Characters.

Oracle     Query Complexity      LB     Query Length     Adaptive?     #EC      Level of Recovery     Positions

Edit            $\revise{2k \log (n/k) + k + \log n + c}$ or $n+2$       $\Tilde{\Omega}(n)$     $\mc{O}(n)$      Adaptive      0     Exact sequence     Theorems <ref>&<ref>

Edit            $n+1$       $\Tilde{\Omega}(n)$     $\mc{O}(n)$      Non-adaptive      1      Exact sequence     Theorem <ref>

Edit            $\frac{1}{2}(n^2 + 3n)$       $\Tilde{\Omega}(n)$     $\mc{O}(n)$      Non-adaptive      0      Exact sequence     Theorem <ref>

($p$-)DTW             $n+1$       $\Tilde{\Omega}(n)$      $\mc{O}(n)$      Adaptive      1      Exact sequence     Theorem <ref>

($p$-)DTW             $2n$       $\Omega(n)$      $\mc{O}(n^2)$      Non-adaptive      0     Equivalent class      Theorem <ref>

($p$-)DTW             $n^2+n$       $\Tilde{\Omega}(n)$      $\mc{O}(n)$      Non-adaptive      1       Exact sequence     Theorem <ref>

($p$-)DTW             $n+2$       $\Tilde{\Omega}(n)$      $\mc{O}(n)$      Non-adaptive      2*      Exact sequence     Theorem <ref>

$2n - 1$      $2n - 1$     $\mc{O}(n)$      N/A†      0**      Equivalent class     Theorem <ref>

Any distance        $\poly(n)$      -     $\mc{O}(n)$      Adaptive      0     Zero distance to input     Theorem <ref>

0in1.2em† For both adaptively and non-adaptively querying the distance oracle, the optimal bound on the query complexity is $2n-1$.

0in1.2em* Increasing #EC from $2$ to an arbitrary constant cannot improve the query complexity to be better than $\mc{\tilde{O}}(n)$.

0in1.2em** Involving extra characters not only cannot improve the level of recovery from “equivalence class” to “exact sequence”, but also cannot improve the query complexity (see Theorem <ref>).

For a binary alphabet $\bits$ and any input sequence $s \in \bits^i$ where $0 \leq i \leq n$, any algorithm which recovers the sequence $s$ up to equivalence by querying the DTW or distance oracle between $s$ and a set of query sequences requires query complexity at least ${\Omega}(n)$.

We highlight our techniques used in proving this lower bound in Section <ref>, while the formal proof can be seen in Theorem <ref> and Theorem <ref>.

§.§.§ Adaptively Querying Distance Oracles, Optimally

We first answer the distance recovery problem with adaptive query strategies.
Our solutions are summarized in the theorem below.

For a binary alphabet $\bits$ and any input sequence $s \in \bits^i$ where $0 \leq i \leq n$, there exists an algorithm which can exactly recover the input sequence $s$, by adaptively querying the distance oracle (for the edit and DTW distances) between $s$ and a set of query sequences with query complexity at most $\mc{O}(n)$.

All results in Theorem <ref> match our lower bounds on the query complexity.
Without extra character(s), using the DTW distance oracle we can only recover a sequence in the same equivalence class.
Our result in Theorem <ref> for the DTW distance is achieved with the assistance of $1$ extra character outside the alphabet $\{0,1\}$, and the proof and algorithm can be found in Theorem <ref>.

For the edit distance, we have two different adaptive algorithms that can achieve the $\mc{O}(n)$ bound.
The first algorithm makes use of the property that, for two sequences, the edit distance is equal to the difference in their lengths, if and only if one sequence is a subsequence of the other.
We construct an $\mc{O}(n)$ adaptive query set and a binary search algorithm utilizing this property to recover the input sequence.
Our second algorithm instead queries the length of the input sequence by an empty sequence and then finds a set of $\mc{O}(n)$ bases as the query set, from which we can reconstruct the input sequence.
These are further detailed in Theorem <ref> and Theorem <ref>.

For the distance, adaptive and non-adaptive strategies are essentially the same, because we prove that $2n-1$ queries are necessary and sufficient for recovering from a distance oracle.
However, we can only recover a sequence in the equivalence class in this setting. This result is described as a non-adaptive query strategy in Theorem <ref>.

§.§.§ Non-adaptively Querying Distance Oracles, Optimally

Next we describe our non-adaptive query strategies for the distance recovery problem.
Theorem <ref> shows upper bounds for exact sequence recovery, while Theorem <ref> summarizes our results on the recovery problem of finding a sequence in the same equivalence class as the input sequence.

For a binary alphabet $\bits$ and any input sequence $s \in \bits^i$ where $0 \leq i \leq n$, there exists an algorithm which can exactly recover the input sequence $s$, by querying the distance oracle (for the edit and DTW distances) between $s$ and a non-adaptive set of query sequences with query complexity at most $\mc{O}(n)$, with the assistance of $\mc{O}(1)$ extra characters in the query sequences.

With $1$ extra character, we show the construction of a set of non-adaptive queries that can exactly recover sequences from the edit distance (Theorem <ref>), while with $2$ extra characters, we can exactly recover input sequences from the DTW distance (Theorem <ref>).
Both results match our lower bound on the query complexity, while we complement our results with an $\mc{O}(n^2)$ query complexity algorithm for the DTW distance with $1$ extra character (Theorem <ref>).
We note that non-adaptive strategies have limited power compared to adaptive strategies. Hence, we consider adding extra characters to construct query strategies that are comparable to the lower bounds.
For the edit distance, introducing more than $1$ extra characters cannot encode more information in the query results, because the cost between $0$ (or $1$) and any other additional character is always the same.

For a binary alphabet $\bits$ and any input sequence $s \in \bits^i$ where $0 \leq i \leq n$, there exists an algorithm which can recover the sequence in the same equivalence class as the input sequence $s$, by querying the distance oracle (for the DTW and  distances) between $s$ and a non-adaptive set of query sequences with query complexity at most $\mc{O}(n)$, without extra characters in the query sequence.

By Theorem <ref>, if we are not allowed to use extra characters, we can only recover the sequence in the same equivalence class as the input sequence for the DTW distance.
Our query construction and proof are shown in Theorem <ref>.
We also remark that for distance,
using extra characters cannot help to improve the results of Theorem <ref>, as shown in Theorem <ref>.

The main technical results of this paper are summarized in Table <ref>.

§.§ Paper Roadmap

The remainder of the paper is organized as follows.
Section <ref> introduces the notations and essential background definitions (regarding sequence, distances, and matching properties) used in this paper.
Section <ref> highlights the techniques and insights behind our proofs of non-adaptively querying the DTW distance oracle, which helps the understanding of the most non-trivial and interesting parts of this paper.
Section <ref> consists of our results on the recovery problem with adaptive queries, which begin with a general framework for all non-decomposable distances and follow by instantiations as per distance using specific properties.
We present and discuss our results on the lower bounds and upper bounds of query complexity for recovery with non-adaptive queries on edit distance, DTW distance, and distance, with different recovery guarantees, in Section <ref>, Section <ref> and Section <ref>, respectively.
Section <ref> summarizes the related papers to our problem.
As an initiation of this line of study in the recovery of non-decomposable distances, we finally describe the yet-open problems in Section <ref>.

§ PRELIMINARIES

notation-0We would like to briefly introduce the fundamental concepts, definitions and notations that are involved in this paper. An alphabet is a finite set of characters. A binary alphabet contains two elements, $\Sigma_b \coloneqq \bits$. A sequence is either empty $\phi$, or an enumerated collection of characters selected from a given alphabet.
We denote the length of a sequence $s$ by len-op-0$\revise{\len}(s)$.
Throughout the paper, we use $[n]$ to denote the set $\{ 1, 2, \dots, n \}$.
Then for sequence $s$, $[\len(s)]$ represents its indices set.
Note our indices set starts from 1.

A distance function between a pair of sequences measures the similarity and the structural relationship between them.
A distance function $\dist(\cdot, \cdot)$, as a metric, satisfies the following properties:

* Identity: $\dist(s, s') = 0$ iff $s = s'$;

* Commutativity: $\dist(s, s') = \dist(s', s)$;

* Triangle inequality: for any sequence $x$,
$\dist(s, s') \leq \dist(s, x) +  \dist(x, s')$;

* Non-negativity: $\dist(s, s') \geq 0$.

Different distance functions can capture the similarity information from different perspectives.
While we use $\dist(\cdot, \cdot)$ to denote the distance metric in general, in this paper we are in particular interested in the edit distance (denoted by $d_L(\cdot, \cdot)$, $L$ for Levenshtein), ($p$)-Dynamic Time Warping ($p$-DTW) distance (denoted by $d_{\DTW}(\cdot, \cdot)$), and distance (denoted by $d_F(\cdot, \cdot)$), which are non-decomposable to a sum of coordinate-wise contributions.
We note that the widely used DTW distance is not a metric because identity and triangle inequality properties do not hold for it.
It has been shown a generalization to $p$-th power of DTW (i.e., $p$-DTW) distance satisfies weak triangle inequality up to a factor parameterized by $p$ and the sequence length [Buchin et al., 2022].
We discuss in this paper how the missing triangle inequality affects our recovery problem (especially for DTW).

There are several other definitions related to sequences that are useful in our paper.

Summary of Main Notations

Notation     Meaning of Notation      Notation     Meaning of Notation

$s$     The input sequence     $\phi$     The empty sequence

$s[i]$     The $i$-th character of sequence $s$     $s[i, j]$     A substring of $s$ (from the $i$-th to the $j$-th character)

$c^m$     Repeating character $c$ for $m$ times      $\len(s)$     The length of $s$

$[n]$     $\{ 1, 2, \ldots, n \}$      $[\len(s)]$     The index set of $s$

lor($s, i$)     The length of the $i$-th run of $s$     #runs($s$)     The number of runs in $s$

$\mc{Q}$     Query set     $q^{(i)}$     The $i$-th query in the query set

$\dist(\cdot, \cdot)$     The general distance oracle     $d_L(\cdot, \cdot)$     The edit distance oracle

$d_{\DTW}(\cdot, \cdot)$     The DTW distance oracle     $d_F(\cdot, \cdot)$     The distance oracle

$\MSS(seq, r)$     A MSS instance     $\| \cdot \|_p$     $\ell_p$ norm

The runs of a sequence $x$ are the maximal substrings consisting of a single
repeated character. Any sequence obtained from $x$ by extending $x$’s runs is an expansion of $x$.
For a given character $c$, we use $c^{m}$ to represent the sequence obtained by repeating $c$ for $m$ times.
We denote the length of the $i$-th run of $x$ by lor($x, i$), where lor means Length of Run function, and the number of runs of a sequence $x$ by #runs($x$).

The following definitions of a condensed expression and subsequence are useful in developing our algorithms.

We say $y$ is a condensed expression of $x$ if (i) $y$ has the same number of runs as $x$, (ii) the first and last character of $y$ and $x$ are the same, (iii) each run of $y$ only has 1 character.

Given a sequence $y$, its subsequence $x$ is derived by deleting zero or more characters from $y$ without changing the order of the remaining characters.
The substring $x'$ is a contiguous subsequence of $y$.
We use $x[a]$ to denote the $a$-th character of the sequence $x$, and $x[a, b]$ to denote a substring of $x$ which starts from the $a$-th character and ends at the $b$-th character.

As an example, consider the sequence $0010111$.
The number of runs in this sequence is $4$.
The runs of sequence $0010111$ are $00$ (the 1st run), $1$ (the 2nd run), $0$ (the 3rd run), and $111$ (the last run), with length of $2, 1, 1, 3$, respectively.
By duplicating the characters, we can extend a run in a sequence and then obtain another sequence which is an expansion of the original one.
For instance, by extending the second run in $0010111$, we get $0011110111$ which is the expansion of sequence $0010111$.
The condensed expression of $0010111$ is the sequence $0101$.
Sequences $010$, $101$, $0111$ are subsequences (or substrings) of $0010111$, while $01111$, $000$, $1111$ are only subsequences (not substrings).

The definitions of these three distances (Edit, DTW, and ) are listed as follows.

Given two sequences $x$ and $y$, the edit distance $d_{L}(x, y)$ equals the minimal number of edit operations required for a sequence $x$ to be transformed to sequence $y$.
Specifically, we consider the Levenshtein distance  [Levenshtein, 1966] which captures the addition, deletion, and substitution of single symbols.

l1_absWe use $\| \cdot \|_1$ or simply $\| \cdot \|$ to denote the $\ell_1$ norm distance between two equi-length sequences whose symbols are real numbers. The notation for absolute value $|\cdot|$ is used to calculate the cost or difference between two characters.

DTW-definitionConsider two sequences $x, y$ of length $m_1$ and $m_2$, respectively. A correspondence $(\overline{x}, \overline{y})$
between $x$ and $y$ is a pair of equal-length expansions of $x$ and $y$. The cost of a correspondence is calculated as the $\ell_1$ distance between $\overline{x}, \overline{y}$: $\| \overline{x} - \overline{y}\|_1$. A correspondence between $x$ and $y$ is said to be optimal if it has the minimum attainable cost, and the resulting cost is called the dynamic time warping distance $d_{\revise{\DTW}}(x, y)$, that is
d_{\revise{\DTW}}(x, y) = \min_{(\overline{x}, \overline{y}) \in \mc{W}_{x, y}} \| \overline{x} - \overline{y}\|_1,
where $\mc{W}_{x, y}$ denotes the set of all correspondences $(\overline{x}, \overline{y})$.

By replacing the $\ell_1$ norm in Definition <ref> with the $\ell_p$ norm ($1\le p<\infty$), we obtain the definition for the $p$-DTW distance.

For any $m_1, m_2 \in \mbb{N}$, let $x, z \in X^{\leq m_1}, y \in X^{\leq m_2}$, and $1 < p < \infty$. Then, we have the following inequality,

d_{\revise{\DTW}_p}(x, z) \leq m_1^{1/p} \cdot \big( d_{\revise{\DTW}_p}(x, y) + d_{\revise{\DTW}_p}(y, z) \big).

In addition to the existing definitions, we need to introduce some new concepts essential to our proofs for ($p$)-DTW distance.

ind-1Recall that the indices set of sequence $x$ is denoted by $x.\text{indices} \coloneqq [\len(x)]$.
We say a sequence $x$ is monotonic, if for every $i, j \in \revise{[\len(x)]}$, $i < j \Rightarrow x_i \leq x_j$, or for every $i, j \in \revise{[\len(x)]}$, $i < j \Rightarrow x_i \geq x_j$, where $x_i$ denotes the $i$-th character in $x$.

Consider the query sequence $q$ and the input sequence $s$ as two vertex sets $(U =\{ u_1, \dots, u_\ell \}, V = \{ v_1, \dots, v_n \})$ where the vertex set $U$ denotes the characters in sequence $q$ and the vertex set $V$ denotes the characters in sequence $s$.
Let $M$ be an edge set that for each $m \coloneqq (u, v) \in M$, we have $u \in U$ and $v \in V$.
We say M_s_q_0$M(q, s)$ is a matching (or simply $M$ when the context is clear) between $q$ and $s$ (or $U$ and $V$) if $M$ satisfies the following properties:

1) every vertex in $U$ and $V$ corresponds to at least one edge in $M$;

2) the first character in $U$ is matched to the first character in $V$ and the last character in $U$ is matched to the last character in $V$;

3) the indices of matched character pairs are monotonic, i.e., for any two edges $(u_i, v_j), (u_k, v_l) \in M$, $i > k \Rightarrow j\geq l$ and $j > l \Rightarrow i \geq k$.

We define the degree of a vertex, $\revise{\deg}(u_i)$ or $\revise{\deg}(v_j)$, as the number of associated edges in a matching $M$.

The cost of an edge $m \coloneqq (u_i, v_j) \in M$ is defined to be the $\ell_1$ norm distance $\revise{\Cost}(m) \coloneqq \| u_i - v_j \|$.
The cost of a matching is defined as $\revise{\Cost}(M) \coloneqq \sum_{m \in M} \revise{\Cost}(m)$.
Let $\mc{M}$ consist of all possible matchings between $q$ and $s$ (or $U$ and $V$).
If a matching $M \in \mc{M}$ has minimal cost on the edges, that is $\revise{\Cost}(M) = \min_{M_i \in \mc{M}} \revise{\Cost}(M_i)$, we call this matching a DTW matching.
A DTW matching yields a DTW distance between $q$ and $s$.

easy_matchingBased on our definitions, the concepts of matching provide a different perspective of the non-decomposable distance.
A matching between two vertex sets defines a possible alignment between two sequences with different lengths.
The notion of DTW matching better captures the graph-theoretical properties of the implicit optimal alignment in computing DTW distance than the conventional definition.
The cost of a DTW matching is equal to the DTW distance between two sequences which are constituted by the vertex sets respectively.
We note that there might exist multiple DTW matchings (of equal cost) between a pair of sequences.

Given input sequence $s$ of length $\ell$, two query sequences $q$ and $q'$ of length $n$ and two corresponding matchings $M$ (between $q$ and $s$) and $M'$ (between $q$ and $s'$).
We say $M$ and $M'$ are isomorphic if,
$\forall 1 \leq i \leq \ell$ and $\forall 1\leq j \leq n$, edge $(s_i, q_j)\in M$ $\iff$ edge $(s_i, q_j') \in M'$.

By replacing the $\ell_1$ norm in Definition <ref> with the  $\ell_\infty$ norm, we obtain the definition of the distance.

The distance in our paper is equivalent to the discrete distance in the prior works of [Eiter and Mannila, 1994, Aronov et al., 2006].

Extended alphabet.
extended_alphabetSince in this paper we discuss recovery sequence based on distance queries from binary or extended alphabet, we would like to note that the distance definitions are independent of the alphabets. That being said, while we study the problem by restricting the input sequence as drawn from the binary alphabet (which generalizes to any constant-sized alphabet by applying coding methods), we do not change the distance definitions in a skewed way of embedding special symbols on the extended alphabet or backdoors to the oracle.
To ensure that the distance output makes sense, we specify the extended alphabets for queries to the different distance oracles.
For edit distance, the extended alphabet can contain any symbol outside the binary alphabet, as the edit distance oracle counts the edit operations no matter what symbol is used.
For ($p$-)DTW distance and distance, the extended alphabet can consist of any real number. This makes sense because the DTW and distances are defined based on $\ell_p$ or $\ell_\infty$ cost.

The main notations used in this paper are summarized in Table <ref>.

§ OUR TECHNIQUES

In this section, we summarize and highlight the main technical insights behind our results on non-adaptive recovery from the DTW distance oracle, which are the most non-trivial and interesting parts of this paper.
We hope to convey our intuitive ideas in a less formal manner before diving into the full proofs in the later sections.
Reader may skip this section if they are looking for the complete statements and proofs of these results.
In particular, we will cover the intuitions behind the following four theorems.

There exists a pair of input sequences $s$ and $s'$ such that for any query sequence $q$, $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$. That is, $s$ and $s'$ cannot be distinguished by DTW Distance Oracle queries without using extra characters.

Theorem <ref> shows the impossibility of only using binary sequences to recover the input sequence from the DTW distance oracle.
If two input sequences cannot be distinguished, we say that they are in the same equivalence class.
The following two informal theorems state the upper bound and lower bound on DTW distance recovery up to the equivalence class.

There exists a query set $\mc{Q}$ consisting of $\mc{O}(n)$ queries of length $\mc{O}(n)$, such that any two distinguishable input sequences can be distinguished by $\mc{Q}$.

query-construct-0$\mc{Q}$ is designed to contain all queries with $i$ runs, for any $i \in [1, n]$.

For the binary alphabet $\bits$, any algorithm to recover an arbitrary input sequence $s \in \bits^\ell$, where $0 \leq \ell \leq n$, up to its equivalence class, by querying the DTW distance to a set of sequences, has query complexity  $\Omega(n)$.

Note that our upper bound matches the lower bound for DTW equivalence class recovery. The next exciting finding is that, using queries that contain a small number of extra characters, we can exactly recover the input sequence.

By introducing $\mc{O}(1)$ extra characters to the query sequence alphabet, we can recover any input sequence of length $\leq n$ with $\mc{O}(n)$ DTW queries.

We aim to recover the given input sequence (of length $\leq n$) with the minimum number of queries for different distance metrics.
Theorems <ref>, <ref> and <ref> summarize the best results one can hope to obtain for recovering sequences from a DTW oracle without extra characters, i.e., identifying the equivalence class that the input sequence belongs to.
If we are allowed to use extra characters in the query construction, we can distinguish and recover all the sequences with $\mc{O}(n)$ queries, as informally stated in Theorem <ref>.
We summarize and highlight the techniques used in proving these theorems in the rest of this section, in which the informal proofs are grouped as follows.
In Section <ref>, we show proof sketches on recovery of sequences using binary queries, which include results from Theorems <ref>, <ref> and <ref>.
In Section <ref>, we give a bird's-eye view over the key ideas of the query construction and proof of Theorem <ref>.

Constructing a matching between $q$ and $s'$ based on the matching between $q$ and $s$.

§.§ Optimal Non-adaptive Strategy using DTW Queries over Binary Alphabet

The hardness result (Theorem <ref>) is shown by finding evidence of such a pair of indistinguishable input sequences.

Informal proof for Theorem <ref>. In the case of DTW Distance, we discover that it is actually impossible to recover any given input with an arbitrary number of queries.
For example, the input sequences $s = 010110$ and $s' = 011010$ cannot be exactly recovered, since they cannot be distinguished by any query sequence. To see this, the idea is that $d_{\revise{\DTW}}(1, r) = d_{\revise{\DTW}}(11, r)$ for any non-empty sequence $r$, unless $r = 0$. Therefore, a DTW matching between $s$ and any query sequence $q$ would yield a corresponding matching between $s'$ and $q$ with the same cost, (see Figure <ref> as an example) and vice versa.
(Refer to Theorem <ref> for detailed proof). This implies that $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$, and thus $s$ and $s'$ cannot be distinguished by $q$.

Before giving the intuition for the proof of Theorem <ref> and <ref>, we first introduce the notion of a Min 1-Seperated Sum (MSS) problem [Abboud et al., 2015, Schaar et al., 2020], where each instance of the DTW distance computation can be reduced to solving a corresponding instance of MSS problem.
The reduction plays the role of an important primitive in our proofs.

MSS Problem. The min 1-separated sum (MSS) problem takes as input a sequence $seq$ of $m$ positive integers and an integer $r \geq 0$. The problem is to select $r$ integers from $seq$ and minimize their sum, under the constraint that any two adjacent integers cannot be selected simultaneously. We say $\MSS(seq, r)$ is an MSS instance.

Let $x \in\{0,1\}^{m}$ and $y \in\{0,1\}^{n}$ be two binary strings such that $x[1]=y[1], x[m]=y[n]$, and $\#\textsc{runs}(x) \geq\#\textsc{runs}(y)$. Then, the DTW distance between $x$ and $y$, i.e., $d_{\revise{\DTW}}(x, y)$, equals the sum of a solution for the MSS instance $\MSS\biggl(\Bigl(\textsc{lor}(x,2), \ldots,\textsc{lor}(x, \#\textsc{runs}(x)-1)\Bigl), \frac{(\#\textsc{runs}(x)-\#\textsc{runs}(y))}{2} \biggl)$.

To give an example of the reduction, let $s = 010110$ and $q = 010$.
By mis-refTheorem <ref>, we obtain $d_{\revise{\DTW}}(s, q) = \revise{\MSS}((1, 1, 2), 1)$.
For ease of presentation, we will use $\revise{\MSS}(x ,(\#\textsc{runs}(x)-\#\textsc{runs}(y)) / 2)$ to represent the same MSS instance.

(a) Illustration of input-uniqueness and 0/1-uniqueness; (b) Illustration of isomorphism and performing a difference operation, compared to Fig (a); (c) Illustration of shifting operation.

Remark. For binary strings $x \in \{0, 1\}^m, y \in \{0, 1\}^n$ where $x[1]\neq y[1]$ or $x[m] \neq y[n]$, we can still reduce $d_{\revise{\DTW}}(x, y)$ to an MSS instance (which will be presented later in the paper using another technique from [Schaar et al., 2020]). In this section, where we only illustrate the main idea of the proofs, we will only consider the case where the input sequence and query sequence each have the same starting character and the same ending character (so Theorem <ref> can be directly applied), and other cases can be resolved similarly. For full details, we defer to later sections.

Intuition for Theorem <ref>.
We would like to skip the proof sketch for Theorem <ref>, but just to mention the insights of the query construction to obtain such an orderwise optimal query complexity upper bound.
The set of queries $\mc{Q}$ contains queries of all possible combinations of runs in the input sequence. That is, for the maximum length $n$ of the input sequence, the set of the possible number of runs is $[n]$.
This gives us $n$ queries. Since we have 0 runs and 1 runs, there are $2n$ queries in the query set $\mc{Q}$ in total.
Then the remainder of the proof is to perform case analysis –  we first eliminate obvious cases and then build a mapping to the corresponding MSS instances such that if any pair of sequences cannot be distinguished by $\mc{Q}$, they cannot be distinguished by any binary queries.

Informal proof of Theorem <ref>.
query-construct-1Recall our query set $\mc{Q}$ contains queries of all numbers of runs.
The intuition for the proof of Theorem <ref> is that, for each given constant-length interval of the number of runs, we can construct a certain pair of input sequences which can only be distinguished by queries with a number of runs within this interval. For instance, it can be proved that $s_1 = 01^301^30^31^30^31^30$ and $s_2 = 01^30^21^30^21^30^31^30$ can only be distinguished with queries with a number of runs within $[4, 10]$. Thus, an  $\Omega(n)$ number of such constructed pairs of input sequences can correspond to $\Omega(n)$ disjoint intervals, yielding an $\Omega(n)$ lower bound for this problem.

We now construct a class of pairs of input sequences $(s, s')$ where $s$ and $s'$ share the same starting and ending character, such that $s$ and $s'$ can only be distinguished by queries $q$ with a number of runs within $[\#\textsc{runs}$(s)$+c_1, \#\textsc{runs}$(s)$+c_2]$ for two constants $c_1<c_2$. According to Theorem <ref>, as long as the constructed pair of input sequences $(s, s')$ have the same number of runs, for a query $q$ with more than #runs$(s)$ number of runs, $d_{\revise{\DTW}}(q, s)$ and $d_{\revise{\DTW}}(q, s')$ are only determined by the query $q$ and #runs$(s)$, and thus $q$ cannot distinguish $s$ and $s'$. For a query $q$ with fewer than #runs$(s)$ number of runs, $d_{\revise{\DTW}}(q, s)$ and $d_{\revise{\DTW}}(q, s')$ are reduced to two MSS instances. Note that for different queries $q$, the sequences (i.e., the first parameter) of MSS instances remain the same, while #runs($q$) determines the number of elements selected in the sequences of MSS instances (i.e., $(\#\textsc{runs}(s) - \#\textsc{runs}(q))/2$). We hope to construct a pair of sequences $seq$ and $seq'$ such that $\revise{\MSS}(seq, 1)\neq \revise{\MSS}(seq', 1)$ and $\revise{\MSS}(seq, x) = \revise{\MSS}(seq', x)$ for all $x>1$: let $seq$ and $seq'$ be the sequences corresponding to MSS instances of $s$ and $s'$; in this way, $s$ and $s'$ would still be distinguishable because $\revise{\MSS}(seq, x)\neq \revise{\MSS}(seq', x)$ for $x=1$, but any query $q$ with fewer than #runs$(s)-4$ runs cannot distinguish $s$ and $s'$ because $\revise{\MSS}(seq, x) = \revise{\MSS}(seq', x)$ for all $x\ge 2$, where $x=(\#\textsc{runs}(s) - \#\textsc{runs}(q))/2$.

§.§ Optimal Non-adaptive Strategy using DTW Queries with Extra Characters

We show that, if we augment the ability of our oracles by introducing extra characters, we can solve the DTW distance oracle recovery problem with optimal query complexity up to polylogarithmic factors.

Informal proof of Theorem <ref>.
We would like to construct a query set of size $\mc{O}(n)$ that can recover the input sequence using a DTW distance oracle.
A natural idea is to retrieve information about the input sequence by differentiating-1taking the difference between the query results of neighbouring queries (i.e., queries only differing by $1$ character).
To achieve this, we construct a query set satisfying the following three properties:

1) Isomorphism:
The matchings corresponding to neighboring queries should be isomorphic. Fig. <ref> (a) and Fig. <ref> (b) show an example of isomorphism, where only one character of the input sequence is changed, while the structure of both optimal matchings remains identical.
With this property, we know that the difference between the query results of neighboring queries only reflects the effects of the different characters in neighboring queries.
This property is the essence of guaranteeing the correctness of differentiating-2the difference operation.

2) Input-uniqueness:
Each character in the query sequence should be matched to exactly $1$ character in the input sequence.
Another way to think of this property is to imagine a total function that maps the entire query sequence to the input sequence.
Each matching between the query and input defines such a function so that we can extract information about the input by knowing something about the function.
With this property, we can differentiating-3take the difference to get the information of a single character in the input sequence with a pair of neighboring queries. Note that if the differing character in the neighboring queries is matched to multiple characters in the input sequence, the difference in the query results can only reflect the sum of the costs over these characters, which makes exact recovery hard. Take Fig. <ref> (a) and Fig. <ref> (b) as an example.
Input-uniqueness is satisfied for both Fig. <ref> (a) and Fig. <ref> (b), since all characters in the query sequences of both figures have degree $1$.
Denote the matchings from Fig. <ref> (a) and Fig. <ref> (b) by $M_a$ and $M_b$ respectively.
Since $M_a$ has cost $3(1-a) + 2a + b$ while $M_b$ has cost $2(1-a) + 2a + (1-b) + b$, we know that $\revise{\Cost}(\needreview{M_a})-\revise{\Cost}(\needreview{M_b}) = b-a$.
By differentiating-4taking the difference, we can infer that $s[4] = 1$; otherwise, if $s[4]= 0$, we would have $\revise{\Cost}(\needreview{M_a})-\revise{\Cost}(\needreview{M_b}) = (a-0) - (b-0) = a-b$.

Combining properties 1) and 2), we note that each character in the input sequence can match to $1$ or more characters in the query sequence, so we can obtain an expansion of the input sequence.
Based on the example, Fig. <ref> (a) and Fig. <ref> (b), we can obtain an expansion, $110010$, of the input sequence.
We can then infer that the input sequence is of the form $1^x0^y10$, where $x, y \in [1, 2]$.
To recover the exact input sequence, we require more information given by the following third property.

3) 0/1-uniqueness:
In an optimal matching w.r.t. our constructed queries, either all 0's or all 1's in the input sequence have degree 1.
Using this property, we can locate the exact position of either all 0's or all 1's in the input sequence, and exactly recover the input sequence by combining the two cases.
In the example of Fig <ref>, 1-uniqueness is satisfied in Fig. <ref> (a) and Fig. <ref> (b), while 0-uniqueness is not, since $s[3]$ in both figures has degree 2.
According to 1-uniqueness, we can reduce the form of the input sequence from $1^x0^y10$ to $110^y10$.
Similarly, we can construct another set of queries that satisfies 0-uniqueness to locate the positions of 0's in the input sequence, which determines $y$ in this example.

Sequence Monotonicity $\rightarrow$ Input-uniqueness.
We observe that property 2) can be obtained from a monotonic design of the query sequences.

Given a monotonic sequence $q$ of length $n$ where

\begin{equation}
\min_{i\in [n]}\max\{|q[i]-0|, |q[i]-1|\} > \max_{i,j\in [n]}|q[i]-q[j]|,\label{equ:single_direction_o1_intro}
\end{equation}

for any input sequence $s$ with length $\ell \leq n$, given a DTW matching $M$ for $(q,s)$, we have $\revise{\deg}(q[i]) = 1$ for all characters $q[i]$ in $q$.

The intuition for Lemma <ref> is that, with the monotonic property and equation (<ref>) guaranteed in our query construction, we can ensure that there do not exist characters $s[i]\in s$ and $q[j] \in q$ where $\revise{\deg}(s[i])>1$ and $\revise{\deg}(q[j])>1$ are satisfied at the same time. Fig <ref> in a later section illustrates that, for such a pair of $s[i]$ and $q[j]$, we can always construct a matching with lower cost where one of their degrees is decreased to $1$. Therefore, either all characters in $s$ or all characters in $q$ would have degree $1$. Since $\revise{\len}(q) = n \geq \revise{\len}(s)$, we know that $\revise{\deg}(q[i]) = 1$ for all characters $q[i]$ in $q$.

Fig. <ref> (a) and Fig. <ref> (b) satisfy sequence monotonicity, since the query sequences in both figures are monotonic sequences of length $n$ and for $x$ in $\{1, 2\}$, $\min_{i\in [n]}\max\{|q^{(x)}[i]-0|, |q^{(x)}[i]-1|\} = \frac{3}{5}> (\frac{2}{5} - \frac{1}{3}) = \max_{i,j\in [n]}|q^{(x)}[i]-q^{(x)}[j]|$.

Sequence 0/1-preference $\rightarrow$ 0/1-uniqueness.
We observe that property 3) can be guaranteed by the 0/1-preferred design of the query sequences.
If all characters in the query sequence are less than (or greater than) $\frac{1}{2}$, then we can guarantee 1-uniqueness (or 0-uniqueness) of the input sequence.
Intuitively, this would hold because, if all characters in the query sequence are less than (or greater than) $\frac{1}{2}$, matching them to 0's (or 1's) in the input sequence yields lower cost than matching to 1's (or 0's).
Fig. <ref> (a) and Fig. <ref> (b) satisfy 0-preference, since all characters in query sequences (either $a = \frac{1}{3}$ or $b= \frac{2}{5}$) are less than $\frac{1}{2}$.

Query Construction. We now propose the following design of the query sequence.
We first need a single 0 query and a single 1 query to obtain the number of 1's and 0's in the input sequence.
Let $a, b$ be two fractional characters that satisfy $0 < b-a < a < b < \frac{1}{2}$ and the denominators of $a, b$ are co-prime.
Without loss of generality, we can assume $a = \frac{1}{3}$ and $b = \frac{2}{5}$.
We will use $a, b$ as the extra characters to construct the query sequences.
In particular, the rest of the query sequences (other than the $0$ query and the $1$ query) consist of queries $\mc{Q}$ in the form of $q^{(i)} = a^{n-i}b^{i}$, where $i = 1, \dots, n$.
This query construction satisfies sequence monotonicity and sequence 0/1-preference properties. Now we need to prove it also satisfies isomorphism.

For any input sequence $s$, there exists an  set of isomorphic matchings $\mc{M}$ where $M_i\in \mc{M}$ is optimal for query $q^{(i)} \in \mc{Q}$.

The position of the first $0$ in $s$ and the length of both sequences can determine the structure of $M_i$.

Lemma <ref> guarantees the isomorphism property of the constructed query set $\mc{Q}$.
Here we construct an isomorphic set of matchings $M_i \in \mc{M}$ such that only the first $0$ in the input sequence has degree greater than $1$, while all other characters in the matching are of degree $1$.
Fig. <ref> (a) and Fig. <ref> (b) are instances of $M_1$ and $M_2$, where the matchings in both figures are isomorphic to each other.

The position of the first $0$ in $s$ and the length of both sequences can determine the structure of $M_i$.

Note that in this construction, the structure of the matchings is only determined by the position of the first $0$ in the input sequence and the length of both sequences (see Fig <ref>).
Since all query sequences in $\mc{Q}$ have the same length, an isomorphism of constructed matchings is naturally guaranteed.

To prove the optimality of the $M_i$,
we introduce the notion of a  “shifting” operation.
Consider two 0's in the input sequence.
If any character between them has degree 1 and the first 0 has degree greater than 1, by running the shifting operation we decrease the degree of the first 0 by 1 and increase the degree of the last 0 by 1, while preserving the degree of all other characters.
Fig. <ref> (c) illustrates an example of the shifting operation.

[Refers to Claim <ref>]
For our constructed query set $\mc{Q}$, a shifting operation would not reduce the total cost of the matching.

[Informal, Refers to Claim <ref>]
Given input sequence $s$, query $q^{(i)}\in \mc{Q}$ and any optimal matching $M_i^*$ between $s$ and $q^{(i)}$, we can obtain $M_i^*$ by applying a series of shifting operations to $M_i$.

Combining the above two claims, we can show that the $M_i$ are always optimal, which proves Lemma <ref>.
So far, the constructed query set satisfies three properties – isomorphism, input-uniqueness, and 0/1-uniqueness.
Further details of our algorithm to recover the input sequence are given in later sections (see Algorithm <ref>).

§ RECOVERY WITH ADAPTIVE QUERIES

§.§ General Framework

coordinate-descentFor a given distance oracle $\revise{\dist}(\cdot, \cdot)$, a constant-sized alphabet $\Sigma$ and any input sequence $s \in \Sigma^i$ where $0 \leq i \leq n$, there exists an adaptive algorithm which returns a sequence $s'$ such that its distance to the input sequence $s$ satisfies $\revise{\dist}(s, s')=0$ using $\poly(n)$ queries, given that the following two conditions are true:

* There exists a positive constant $c$ (independent of $n$), $\forall s \in \Sigma^i, q \in  \Sigma^{\mc{O}(n)}, \text{where}~ \revise{ 0 \leq i \leq n ~\text{and}~ \dist(s, q)>0}$, we can find a sequence $q'$ within $\poly(n)$ queries such that $\revise{\dist}(s, q) \geq \revise{\dist}(s, q') + c$;

* $\forall s \in \Sigma^i, q \in  \Sigma^{\mc{O}(n)}$, $\revise{\dist}(s, q) \leq \poly(n)$.

Proof sketch: The two above conditions naturally imply a local search algorithm. To recover the sequence $q$, we perform the following steps: 1) randomly initialize $q$. 2) find $q'$ such that $\revise{\dist}(s, q) > \revise{\dist}(s, q')$. 3) set $q$ to $q'$ and repeat 2) to 3).
The algorithm terminates if $\revise{\dist}(s, q) = 0$, and outputs the final $q$ as the sequence $s'$.

Since we reduce $\revise{\dist}(s, q)$ by at least a positive constant $c$ in each iteration, and poly-2$\revise{\dist}(s, q) \leq \poly(n)$,  the algorithm terminates in at most poly-3$\poly(n) / c$ iterations.
Therefore, the total number of queries is poly-4$\mc{O}(\poly(n))$.

The above local search algorithm can be applied to all aforementioned distances.
Specifically, the complexity for the edit distance, DTW distance and distance is $\mc{O}(n^2)$, $\mc{O}(n^2)$ and $\mc{O}(n)$, respectively.
A detailed instantiation of the algorithm on these distances can be found in Appendix <ref>.

As stated in the theorem, the objective of this coordinate descent framework is to reduce $\dist(s, s')$ to 0, which reflects our “zero distance to input” recovery guarantee.
We remark that, for distance function which is a metric, this guarantee implies “recover to equivalence class”, while for distances such as DTW where the triangle inequality does not apply, there exist sequences that can be distinguished whereas the distance is 0.
Such an example includes sequence 101 and 1011.

§.§ Edit Distance

We show that a binary input sequence with maximum length $n$ can be adaptively recovered using at most $\revise{n + \log n + c  \in \mc{O}(n)}$ queries to the edit distance oracle (where $c$ is a constant), by the following theorem.

For a binary alphabet $\bits$, and any input sequence $s \in \bits^{\ell}$ with $k$ runs where $0 \leq \ell \leq n$, there exists an adaptive algorithm to recover the input sequence $s$ using at most $2k \log (n/k) + \log n + k + c$ queries $\revise{\mc{Q}}$ of length $\leq n$ and the exact Levenshtein distance of $s$ to each query sequence $q_i \in \revise{\mc{Q}}$, where the query sequences use no extra characters.

The proof makes use of the following claim.

Given two sequences $x$ and $y$, the edit distance $d_{L}(x, y) = |\revise{\len(x)} - \len(y)| $ if and only if $x$ is a subsequence of $y$ or $y$ is a subsequence of $x$.

Proof of claim.
Without loss of generality, we can assume that $\revise{\len(x)} \geq \len(y)$. Since each insertion, deletion or substitution operation can change the sequence length by at most $1$, we have $d_{L}(x, y) \geq t$ where $(t=\len(x) - \len(y))$.
If $y$ is a subsequence of $x$, we can obtain $y$ by performing $t$ deletions on $x$. Since $d_{L}(x, y) \geq t$, we have $d_{L}(x, y) = t$.
If $y$ is not a subsequence of $x$, we show that $d_{L}(x, y) > t$. To transform $x$ to $y$ we would need at least $t$ deletions. Since $y$ is not a subsequence of $x$, we cannot obtain $y$ by merely performing $t$ deletions on $x$, implying that $d_{L}(x, y) > t$.

Next, to prove Theorem <ref>, we observe that for any sequence on a binary alphabet, the first run starts with either 0 or 1.
That is, the dense-1condensed expression of a binary sequence is in the form of $1010...$ or $0101...$.
Let the number of runs be $k$.
The first part of our adaptive recovery algorithm is determining the input sequence's dense-2condensed expression.
To do so, we need the following set of $2n+1$ queries, $\{ \phi, 0, 1, 01, 10, 010, \dots \}$, where the maximum length of the query in this set is $n$.
The length of the input sequence $\ell$ can be determined by querying the empty sequence $\phi$.
The dense-3condensed expression of the input sequence is equal to the query in the query set of maximum length such that $k = \ell - r$, where $k$ is the length of this query and $r$ is the query result from the oracle.
Since we are adaptively querying the oracle, we do not require all $2n+1$ queries.
By using our querying strategy, the query complexity of this part can be reduced to $\log n + c$.
To see this, we take out all $n$ queries beginning with $0$ from the query set and adaptively query the oracle using binary searchrevise_theorem:adaptive_edit_log_n to find the longest query sequence such that the edit distance between this query and the input sequence equals the length difference between two sequences.
Next, we add an $1$ to the left side (or the most significant bit) of the longest query we just selected, then query the oracle to see if the distance is smaller.
The query sequence with the smaller edit distance is therefore the dense-4condensed expression of the input sequence.
Since a $\phi$ query is required at the beginning,
the entire process requires at most $\log n + 2 \leq \log n + c$ queries.

The second part of our algorithm is to recover the sequence from the dense-5condensed expression via expanding each run by inserting $1$'s (or $0$'s) into the corresponding location.
We have obtained the number of runs, which is $k$.
According to the claim, if any one of the runs of the query sequence contains more characters than that of the input sequence, meaning the query sequence is no longer the subsequence of the input sequence, then we can observe from the query results.
Therefore, we can recover the input sequence run by run.
The naïve way of achieving this is to iterate over runs and insert one character per time to a run until scanning and fulfilling the entire sequence, which results in at most $n$ queries.
Combining the first part of recovering the condensed expression, this approach gives us the overall query complexity of $n + \log n + c  \in \mc{O}(n)$.

An alternative approach to recover the runs is to determine the number of characters in each run using line search and binary search.
That is, we increase the number of characters in a run exponentially (by a factor of 2) and then look back to find the exact number by binary search.
Compared to directly using binary search to find the length of the run within the range of $[2, n-k]$, the complexity analysis of our approach can avoid a potential $n\log n$ term.
To give an example of this approach, suppose we have a run of length 13.
To recover this run, instead of using 13 queries by the naïve approach, we can make 7 queries with the following numbers of 1's: 2, 4, 8, 16, 12, 14, and 13, respectively.
For a run with length $m$, the worst-case query complexity of this approach is $\lceil2\log m\rceil$.

Let $t_i$ be the number of characters in each $1$ run or $0$ run.
Then we have $\sum_{i=1}^k t_i = \ell \leq n$.
Since the number of characters in each block can be determined adaptively using line and binary search, we can derive the query complexity of the second part as $\sum_{i=1}^k \lceil 2\log t_i \rceil \leq 2\log (\Pi_{i=1}^k t_i) + k \leq 2\log (\sum_{i=1}^k t_i / k)^k + k \leq 2k \log (n / k) + k$.
The first inequality holds due to the AM-GM inequality.
Combining the two parts of the algorithm, we know that the overall adaptive query complexity for the exact recovery of the sequence is $2k\log (n/k) + k + \log n + c \in \mc{O}(n)$.

In many cases our alternative approach, as shown in the complexity, saves queries.
There are also edge cases that the naïve approach wins the game – for runs with two characters, using binary search requires 3 queries (i.e., queries with 2, 4, 3, characters in this run respectively), while the naïve approach finishes the task with only 2 queries.

For a binary alphabet $\bits$, and any input sequence $s \in \bits^{\ell}$ where $0 \leq \ell \leq n$, there exists an adaptive algorithm to recover the input sequence $s$ using at most $\revise{n + 2  \in \mc{O}(n)}$ queries $\revise{\mc{Q}}$ of length $\leq n$ and the exact Levenshtein distance of $s$ to each query sequence $q_i \in \revise{\mc{Q}}$, where the query sequences use no extra characters.

The adaptive query strategy is the following.
We first use an empty sequence to query the length $\ell \in [n] = \{1, 2, \ldots, n\}$ of the input sequence.
Then we use $\ell + 1 \leq n + 1$ queries: an $e_0 = 0^\ell$ query and a set of $e_i = 0^{i-1}10^{\ell-i}, i \in [\ell]$ queries (all with length $\ell$).

$s[i] = \begin{cases}
0, & \text{if}~~ d_{L}(s, e_0) - d_{L}(s, e_i) \leq 0;\\
1, & \text{if}~~ d_{L}(s, e_0) - d_{L}(s, e_i) = 1.
\end{cases}$

Proof of claim.
If $s[i] = 1$, $d_{L}(s, e_0) - d_{L}(s, e_i) = $ (#1's in $s$) $-$ (#1's in $s - 1$) $ = 1$.
If $s[i] = 0$, $d_{L}(s, e_0) = $ (#1's in $s$).
We show that $d_{L}(s, e_i) \geq $ (#1's in $s$).
First, $d_{L}(s, e_i) \geq $ (#1's in $s$) $-$ (#1's in $e_i$) = #1's in $s$ $-$ 1.
Consider the series of transformations from $s$ to $e_i$:
1) If we only perform substitution on $s$, we need at least #1's in $s$ + 1 operations.
2) Otherwise we show that we have at least one insertion. If we perform at least one deletion operation(s) on $s$, since $s$ and $e_i$
are of the same length, we would need at least one insertion(s) on $s$.
Note that insertions on $s$ cannot reduce the difference of the number of 1's between $s$ and $e_i$.
Thus, we need at least (#1's in $s$ $-$1) extra operations to reduce the difference to $0$ and we have $d_{L}(s, e_i) \geq $ (#1's in $s$ $-$1) $+$1 $=$ #1's in $s$.
Combining these cases, we obtain $d_{L}(s, e_i) \geq $ (#1's in $s$).

By claim <ref>, we can recover the sequence $s$ character by character.

We remark that both results of Theorem <ref> and Theorem <ref> are useful.
Clearly, using $n+2$ queries in the second algorithm is a better strategy than the naïve approach in the first algorithm, which requires $n + \log n + c$ queries.
However, the first algorithm with the binary search approach yields query complexity of $2k \log (n /k) + \log n + 2k + c$.
When the number of runs (i.e., $k$) is small, this result is better than the $n+2$ queries in the second algorithm.

§.§ DTW Distance

For a binary alphabet $\bits$, and any input sequence $s \in \bits^{\ell}$ where $0 \leq \ell \leq n$, there exists an adaptive algorithm to recover the input sequence $s$ using at most $\revise{n + 1  \in \mc{O}(n)}$ queries $\revise{\mc{Q}}$ of length $\leq n$ and the exact DTW distance of $s$ to each query sequence $q^{(i)} \in \revise{\mc{Q}}$, where the query sequences use revise:theorem_3.41 extra character.

Using an adaptive method, for a binary alphabet $\bits$, an input sequence $s \in \bits^i$ where $0 \leq i \leq n$ can be exactly recovered with at most $\revise{n + 1  \in \mc{O}(n)}$ queries to the DTW distance oracle.
We need 1 additional character, which is the fractional character $\frac{1}{2}$, to construct the set of query sequences.
The details are presented as follows.

First, with a single-character query sequence $q^{(1)} = \frac{1}{2}$, we can obtain the length of the input sequence $s$, which is $\ell = 2d_{\revise{\DTW}}(s, q^{(1)})$.

Consider the query $q^{(2)}=0~ (\frac{1}{2})^{\ell-1}$. Note that each $\frac{1}{2}$ in the $q^{(2)}$ corresponds to at least $\frac{1}{2}$ cost in the query result, and we have $d_{\revise{\DTW}}(s, q^{(2)})\geq (\ell-1)/2$. If $s[1] = 0$, then $s[1]$ and $q^{(2)}[1]$ are perfectly matched, so $d_{\revise{\DTW}}(s, q^{(2)}) = (\ell-1)/2$. Otherwise, the first character $0$ in $q^{(2)}$ would correspond to cost $>0$ in the query result, so $d_{\revise{\DTW}}(s, q^{(2)}) > (\ell-1)/2$.
In this way, we can recover $s[1]$.

Now we recover the whole sequence by induction. Suppose we have recovered $s[1,k]$, we show that we can recover $s[k+1]$ with the query sequence $q^{(k+2)} = s[1,k]s[k](\frac{1}{2})^{\ell-k-1}$. Noting that each $\frac{1}{2}$ in $q^{(k+2)}$ corresponds to at least a $\frac{1}{2}$ cost in the query result, we have $d_{\revise{\DTW}}(s, q^{(k+2)})\geq (\ell-k-1)/2$. If $s[k+1] = s[k]$, then $s[1,k+1]$ and $q^{(k+2)}[1,k+1]$ can be perfectly matched, so $d_{\revise{\DTW}}(s, q^{(k+2)}) = (\ell-k-1)/2$. Otherwise, we claim that $d_{\revise{\DTW}}(s, q^{(k+2)}) > (\ell-k-1)/2$. If the cost corresponding to $q^{(k+2)}[k+1] > 0$, we would already have $d_{\revise{\DTW}}(s, q^{(k+2)}) > (\ell-k-1)/2$, so we can assume that the cost corresponding to $q^{(k+2)}[k+1]$ is $0$. Since $q^{(k+2)}[k+1] = s[k] \neq s[k+1]$, we know that $q^{(k+2)}[k+1]$ cannot be matched with $s[k+1]$. Suppose $q^{(k+2)}[k+1]$ is matched with substring $s[u,u+t]$ in the optimal DTW matching, where $t\geq 0$ and $s[u] = s[u+1] = \cdots  = s[u+t] = q^{(k+2)}[k+1] = s[k]$. Since $k+1 \notin [u, u+t]$, we either have $k+1 > u+t$ or $k+1 < u$. If $k+1 > u+t$, since $\forall u+t < j \leq \ell$ we have $s[j]$ matched to a $\frac{1}{2}$, the total cost would be at least $(\ell-(u+t))/2 > (\ell-k-1)/2$. Otherwise if $k+1 < u$, note that $s[1,u]$ are matched to $q^{(k+2)}[1,k+1]$ in the optimal DTW matching. Since $s[k+1]\neq s[k]$, the number of runs in $s[1,k+1]$ would be greater than the number of runs in $q^{(k+2)}[1,k+1]$ by $1$. Thus,  the number of runs in $s[1,u]$ would be greater than the number of runs in $q^{(k+2)}[1,k+1]$ by at least 1, and they cannot be perfectly matched. Therefore, the cost corresponding to $q^{(k+2)}[1,k+1]$ would be greater than $0$, yielding a total cost of greater than $(\ell-k-1)/2$.

By induction, we can recover the input sequence of maximum length $n$ with $n+1$ queries.

§ RECOVERY WITH NON-ADAPTIVE EDIT DISTANCE ORACLE QUERIES

We begin with a lower bound for edit distance.

For a binary alphabet $\bits$, any algorithm to recover an arbitrary input sequence $s \in \bits^\ell$ where $0 \leq \ell \leq n$ by querying the  Levenshtein distance to a set of sequences of length $\mc{O}(n)$  requires a query complexity of $\Omega(n/\log n)$.

For each query of length $\mc{O}(n)$, the result would be an integer $d = \mc{O}(n)$.
edit_lower_rangeWithout loss of generality, assume the query is of length $an+b$ where $a, b$ are non-negative constant integers and $b<n$.
For an arbitrary input sequence with length $\leq n$, the query result falls into the range of $[(a-1)n+b, an+b]$ if $a>0$ (or $[0, n]$ if $a=0$), yielding $n+1$ possibilities.
For $0\leq k \leq n$, the number of different sequences of length $k$ is $2^k$, and the total number of sequences of length no greater than $n$ would be $\sum_{k=0}^{n}2^{k} = 2^{n+1}-1$. Thus, to distinguish all possible sequences, one would need at least $\log_{\revise{n+1}}(2^{n+1}) = (n+1)/\log(n+1) \in \Omega(n/\log n)$ queries.

Note that this information theoretical proof only applies to deterministic algorithms.
Next we give a proof if one is allowed to use a randomized algorithm.
To show this, we introduce a one-way two-party communication game called INDEX.

Consider two players Alice and Bob. Alice and Bob have access to a common public coin and their computation can depend on this. Alice holds an $n$-bit string $x\in \bits^n$ and is allowed to send a single message $M$ to Bob (i.e., this is a one-way protocol). Bob has an index $i \in [n]$ and his goal is to learn $x[i]$, i.e., $\Pr_{r}[\mathcal{O}ut(M)=x[i]]\geq \frac{2}{3}$).

It is shown in [Kremer et al., 1995] that the above problem requires $|M| = \Omega(n)$. To reduce our recovery problem from the INDEX game, let $R$ be an adaptive randomized recovery algorithm which works as follows.
First, Alice randomly selects a query $q_1$ based on the first part $r_1$ of the shared public coin, and computes $d(q_1, x)$. Alice then adaptively selects a set of queries $q_i$, where each $q_i$ is chosen based on disjoint parts $r_1, \ldots, r_i$ of the public coin, as well as the responses $d(q_1, x), \ldots, d(q_{i-1}, x)$ to previous queries. Alice then sends all query results $d(q_i, x)$ to Bob as the message $M$.

We now show that, if the algorithm $R$ is correct w.p. $2/3$, then $M$ contains $\Omega(n/\log n)$ query results.
Given the success probability $2/3$ of $R$, from message $M$, Bob can reconstruct the string $x$ w.p. at least $2/3$, so Bob can learn each bit of $x$ w.p. at least $2/3$.
According to [Kremer et al., 1995], $|M| = \Omega(n)$ bits. Since each distance query result contains at most $\mathcal{O}(\log n)$ bits, it follows that $\Omega(n/\log n)$ queries are required.

§.§ Exact Recovery with Extra Character(s)

We now move on to the analysis of the upper bound for edit distance with the assistance of extra character(s).
The following theorem uses 1 extra character in the extended alphabet to construct query sequences. We note that for edit distance, using more than 1 extra character in the extended alphabet does not help recover the input sequence, because the edit distance oracle only counts the edit operations made from transforming one sequence to another. Different characters result in the same edit cost.

For a binary alphabet $\bits$ and an input sequence $s \in \bits^\ell$ where $0 \leq \ell \leq n$, there exists an algorithm to recover the input sequence $s$, given a set of On_N_1_2$n+1 \in \mc{O}(n)$ query sequences $\revise{\mc{Q}}$ of length $\leq n$ and the exact Levenshtein distance of $s$ to each query sequence $q \in \revise{\mc{Q}}$, where an extra character $2$ is allowed in the query sequences.

Proof of Theorem <ref>.
The intuition of our proof is to build an oracle that returns the number of 1's in the first $j$ characters of the input sequence $s$.
Then querying the oracle with all possible $j$'s (where $j \in [n]$) implies a recovery of the input sequence.
Note that this oracle calls the edit distance oracle as a subroutine.
The following lemma shows the existence of such an oracle.

Let $s \in \bits^{n'}$ be a non-empty sequence with length $\len(s) = n' \leq n$.
Consider a sequence $s' = 1^{j}2^{n-j}$, where $j \in [n']$, and $2$ denotes a random character not in the binary alphabet $\bits$.
Let $k$ denote the number of $1$'s in the substring $s[1, j]$ (i.e., the first $j$ characters of $s$).
Then the edit distance between $s$ and $s'$ is equal to $n-k$.

We prove the lemma in two steps.
First, we prove that the number of operations required in the transformation from $s$ to $s'$ is greater than or equal to $n-k$.
Second, we show the existence of a sequence of operations that transforms $s$ to $s'$ in exactly $n-k$ steps.

To formally prove the first step, we perform a case analysis on the $j$-th character of $s$, i.e., $s[j]$, being 0 or 1.
When $s[j]=0$, the following claim shows $d_L(s, s') \geq n-k$.

If $s[j]=0$, then $d_L(s, s') \geq n-k$.

Proof of claim.
Let $s = [\text{prefix}]0[\text{suffix}]$, where the length of the prefix is $\len([\text{prefix}]) = j-1$.
Recall sequence $s' = 1^{j}2^{n-j}$.
The edit distance between $s$ and $s'$ can be regarded as the number of operations required in the transformation from $s$ to $s'$.
This transformation from $s$ to $s'$ leads to a sequence of operations of insertion, deletion, and substitution.
For an optimal transformation sequence, swapping two adjacent operations in this sequence generates another valid sequence of operations of the same length.
We can therefore assume all the deletion operations are performed in the beginning, and we denote the number of deletions by $d$.
Let $t$ be the number of $0$'s in $[\text{prefix}]$, and
suppose $d \geq t + 1$.
We can assume that all entries in $[\text{suffix}]$ are $1$ and any $0$ is deleted before a $1$ is deleted; indeed, these assumptions will not increase the edit distance.
After the deletion operations, $s$ is a sequence of $n'-d$ 1's.
If $n'-d \leq j$, then we need an additional $n-(n'-d)$ insertions to recover $s'$.
Thus the total cost is $d + n-(n'-d) \geq d + n - j \geq (t + 1) + n - j = n - k $.
It remains to consider the case that $d < t + 1$.
At this point $s$ is a sequence of length $n'-d$ containing $(t + 1)-d$ 0's among its first $j$ entries, and remaining $1$'s.
Since there are no more deletions, any 1's occurring after the $j$-th entry must be substituted to a 2.
There are $(n'-d)-j$ such 1's that each cost $1$.
Also, each of the $(t + 1)-d$  $0$'s among the first $j$ entries costs one for a substitution. Finally, we need at least $n-n'+d$ insertions to obtain equal-length sequences. So the total cost is at least $\underbrace{(d)}_{\text{\#deletions}} + \underbrace{(n-n'+d)}_{\text{\#insertions}} + \underbrace{[(n'-d) - j]}_{\text{\#substitutions of 1's}}  + \underbrace{[(t + 1)-d]}_{\text{\#substitutions of 0's}} = n -j + t + 1 = n - k$.
This completes all cases.

To finish the case analysis, now we consider the case that $s[j]=1$.
We define $s'' = (s[1,j-1]) 0 (s[j+1, n'])$.
Note $s''$ is obtained by substituting the $j$-th character of $s$ from 1 to 0, hence $d_L(s, s'') = 1$.
We have $k$ 1's in $s[1, j]$, so we have $(k-1)$ 1's in $s''[1, j]$.
By Claim <ref>, we have $d_L(s', s'') \geq n-k +1$.
Since edit distance is a metric, by triangle inequality, $d_L(s', s) + d_L(s, s'') \geq d_L(s', s'') \geq n-k + 1$.
Therefore, $d_L(s, s') \geq n - k + 1 -1 = n-k$.

Now, for the second step, we give a valid sequence of operations to transform $s$ to $s'$ in exact $n-k$ steps.
1) insert $2$'s to the end of $s$ such that $s$ and $s'$ have the same length.
This results in $n-n'$ insertions.
2) for every index $i \in [n]$, substitute $s[i]$ to $s'[i]$ if they are different in the first place.
The number of operations is counted as follows.
For $i \in [1, j]$, it requires $j - k$ substitutions since there are $(j-k)$ $0$'s.
For $i \in [j+1, n']$, it requires $n' - j$ substitutions since we need to substitute every character to $2$.
For $i \in [n'+1, n]$, it requires no substitutions.
Therefore, we have $n-n'+j-k+n'-j = n-k$ operations in total.

Query Sequence Construction.

We introduce an additional wildcard character which is not in the input sequence alphabet.
Using this newly introduced character, the $n+1$ query sequences are constructed as follows.
We use an empty sequence together with $n$ sequences of the form of $1^j2^{n-j}$ for $j=1, \ldots, n$ where $2$ denotes a “not-in-the-alphabet” character.

Algorithm to recover input sequence $s$.
We now give an algorithm to recover $s$ using the query sequence set to complete the proof of Theorem <ref>.
From the query result of the empty sequence, we know the length of the input sequence ($n'$).
If $n'=0$, we know the input sequence is empty as well.
Otherwise, consider the query results of the sequences $1^{j}2^{n-j}$, for $j \in [n']$.
By Lemma <ref>, we know the number of $1$'s ($k$) in the first $j$ characters of $s$ ($j \in [n']$), which implies a complete recovery of $s$.
The exact recovery algorithm is presented in Algorithm <ref>.
We note that the order of the query sequences matters.

Remark. Note that the exact length of sequence $s$ is unknown. This algorithm works non-adaptively for any sequence $s$ with length $\leq n$.

§.§ Exact Recovery without Extra Characters

For a binary alphabet $\bits$ and an input sequence $s \in \bits^\ell$ where $0 \leq \ell \leq n$, there exists an algorithm to recover the input sequence $s$, given $\frac{1}{2}(n^2 + 3n) \in \mc{O}(n^2)$ query sequences $\revise{\mc{Q}}$ of length $\leq n$ and the exact Levenshtein distance of $s$ to each query sequence $q_i \in \revise{\mc{Q}}$, without extra characters.

The construction can be obtained by naturally extending the query set in the proof of Theorem <ref> to all lengths $\ell \in [n]$.
This gives us sum-n-n$\sum_{\ell=1}^n (\ell +1) = \frac{1}{2}(n^2 + 3n) \in \mc{O}(n^2)$ queries.

Exact Recovery Algorithm via Queries to an Edit Distance Oracle

Non-adaptive query sequences $\revise{\mc{Q}} = \{ q^{(1)}, q^{(2)}, \dots, q^{(n+1)} \}$;
The edit distance query result from the sequence for recovery to each query sequence $\revise{\mc{R}} = \{ d^{(1)}, d^{(2)}, \dots, d^{(n+1)} \}$.
The sequence for recovery $s$.
$\revise{\mc{Q}}, \revise{\mc{R}}$
sequence = [] Initialize the sequence for recovery.

$i \in [2, n+1]$
sequence.append($d^{(i)} - d^{(i+1)}$)

sequence = $\phi$ if $d^{(1)}=0$, else sequence[1, $d^{(1)}$] $d^{(1)}$ is the distance to the empty string.

s $\coloneqq$ sequence

§ RECOVERY WITH NON-ADAPTIVE DTW DISTANCE ORACLE QUERIES

§.§ Hardness Result without Extra Characters

There exists a pair of input sequences $s$ and $s'$ such that for any query sequence $q$, $d_{\revise{\DTW}}(s, q)$ = $d_{\revise{\DTW}}(s', q)$. That is, $s$ and $s'$ cannot be distinguished by DTW Distance Oracle queries without extra characters.

witnessWe can prove this theorem by constructing a witness pair of input sequences.
Consider the following pair of input sequences: $s = 010110$ and $s'=011010$.
We argue that this pair of input sequences cannot be distinguished by any binary sequence query $q$.

First, for query sequences that only consist of $0$, it is obvious $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q) = 3$.
Then we only need to consider query sequences containing 1('s).
To see $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$ in this case, we will show (1) $d_{\revise{\DTW}}(s, q) \leq d_{\revise{\DTW}}(s', q)$ and (2) $d_{\revise{\DTW}}(s, q) \geq d_{\revise{\DTW}}(s', q)$ hold simultaneously.

Note that the sequence $s$ contains three 1's.
To prove case (1), we show that there exists an optimal DTW matching satisfying the following properties:

a) The first 1 in $s$ is matched to a substring (c.f. Definition <ref>) of $q$ that begins and ends with both 1's;

b) The second 1 in $s$ is matched to a substring of $q$ that begins with 1;

c) The third 1 in $s$ is matched to a substring of $q$ that ends with 1.

To see the existence of such an optimal matching, we would like to show that, if any one of these properties is violated, we can find another matching with at most the same cost that does not violate these properties.
We take property a) as an example to illustrate this.
If a) is violated, then the substring in $q$ that the first 1 in $s$ gets matched to contains at least a $0$ in the beginning or the end, or both.
If this substring contains both a $0$ and a $1$, then we can map the $0$ at the beginning (or in the end) to the $0$ on the left (or right) side to the first $1$ to obtain a matching with lower cost.
We consider the substring that contains only $0$.
In the optimal matching, the first $1$ in $s$ cannot get matched to more than one $0$ because this will yield more cost than necessary.
Then it reduces to the case where $1$ is matched to a single $0$.
In this case, if the left $0$ in $s$ is matched to a substring that contains at least a $1$ in $q$, then matching the first 1 (in $s$) to this (these) 1('s) leads to a matching with lower cost, since the right 0('s) in the substring can be matched to the 0 on the right to the first 1 in $s$.
Then this leaves the discussion for the case that the first “01” in $s$ is matched to a substring with only 0('s) in $q$.
For ease of presentation, we denote this substring by “$ss$-0”.
The second 0 in $s$ can always be matched to $ss$-0 because this will not yield cost and therefore we know in a potential optimal matching the first “010” can be matched to $ss$-0.
Since we know $q$ contains at least a single 1, this(these) 1('s) will be matched to character after the first “010” (i.e., the second 1)  in $s$.
We then argue that we can change this matching to obtain an equally optimal matching without violating the properties:
i) the first 0 in $s$ is matched to the substring before the first 1 in $q$; ii) the first 1 and the second 0 in $s$ are simultaneously matched to the first 1 in $q$; iii) after the first “010” in $s$, the matching does not change.
In this new matching, there is a cost of 1 saved and generated due to the matching changing on the first 1 and the second 0 in $s$, and therefore the overall DTW cost does not change and the matching remains optimal.
For the rest of the properties, the cases and proofs are similar.
We therefore omit the detailed analyses.

Next, we will show that, given the matching (between $s$ and $q$) with these three properties, we can find a matching between $s'$ and $q$ that will generate DTW cost at most $c$ (that is, $d_{\revise{\DTW}}(s', q) \leq c$).
In particular, we give the following reduction in two matchings.

a) All 0's in $s'$ get matched to the same substring in $q$ as all 0's in $s$;

b) The first 1 and the second 1 in $s'$ get matched to the substring in $q$ that matches the first 1 in $s$;

c) The third 1 in $s'$ gets matched to the two substrings in $q$ that match the second 1 and the third 1 in $s$.

By this matching, the cost between $s'$ and $q$ is exactly $c$.
We do not need to know if this matching is optimal for $d_{\revise{\DTW}}(s', q)$ but this shows $d_{\revise{\DTW}}(s', q) \leq c$.
We note that these three properties hold for any query sequence that contains at least a single 1, because the single 1 can be a substring of this query sequence to satisfy the properties.
Thus, this analysis covers all possible cases of a binary query sequence.
By symmetry, a similar construction can be shown for the opposite side and the conclusion is $d_{\revise{\DTW}}(s, q) \geq d_{\revise{\DTW}}(s', q)$.
Combining the two parts of the proof, we obtain that $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$ for any binary query $q$.

§.§ Recovery without Extra Characters w.r.t. Equivalence Classes

As indicated by Theorem <ref>, there exist input sequences that cannot be distinguished by DTW distance oracle queries.
For ease of presentation, we say that any two different input sequences $s$ and $s'$ are distinguishable if $s$ and $s'$ can be distinguished by DTW Distance Oracle queries.
We categorize mutually indistinguishable sequences into equivalence classes.
In this context, using binary queries, the best solution we can provide in this problem setting is to recover those input sequences up to their equivalence class.

characterization_is_hardThe characterization of the set of indistinguishable binary sequences, given a parameterized sequence length $n$, is not so simple to describe (which can be seen from Observation 4 of [Schaar et al., 2020]).
However, we can propose an optimal query strategy in this setting to distinguish all distinguishable sequences and prove optimality by making use of the reduction between the calculation of DTW distance and the min 1-separated sum problem [Abboud et al., 2015, Schaar et al., 2020].
We introduce the necessary results from [Schaar et al., 2020] below and interpret them in our setting.

The min 1-separated sum (MSS) problem takes the inputs of a sequence $\left(b_{1}, \ldots, b_{m}\right)$ of $m$ positive integers and an integer $r \geq 0$.
The problem is to select $r$ integers $b_{i_{1}}, \ldots, b_{i_{r}}$ with $1 \leq i_{1}<i_{2}<\cdots<i_{r} \leq m$ and $i_{j}<i_{j+1}-1$ for all $1 \leq j<r$ such that $\sum_{j=1}^{r} b_{i_{j}}$ is minimized.
We say $((b_{i_{1}}, \ldots, b_{i_{r}}), r)$ is an MSS instance.

Let $x \in\{0,1\}^{m}$ and $y \in\{0,1\}^{n}$ be two binary strings such that $x[1]=y[1], x[m]=y[n]$, and $\#\textsc{runs}(x) \geq\#\textsc{runs}(y)$. Then, the DTW distance between $x$ and $y$, i.e., $d_{\revise{\DTW}}(x, y)$, equals the sum of a solution for
$\MSS\biggl(\Bigl(\textsc{lor}(x,2), \ldots,\textsc{lor}(x, \#\textsc{runs}(x)-1)\Bigl), (\#\textsc{runs}(x)-\#\textsc{runs}(y))/2 \biggl)$.

For ease of presentation, we will use $\revise{\MSS}(x, (\#\textsc{runs}(x)-\#\textsc{runs}(y))/2)$ to represent the same MSS instance.

Let $x \in\{0,1\}^{m}, y \in\{0,1\}^{n}$ with $m^{\prime}:=\#\textsc{runs}(x) \geq n^{\prime}:=\#\textsc{runs}(y)$. Further, let $a:=\textsc{lor}(x,1), a^{\prime}:=\textsc{lor}(x,m^{\prime}), b:=\textsc{lor}(y,1)$, and $b^{\prime}:=\textsc{lor}(y,n^{\prime})$. The following holds:

If $x[1] \neq y[1]$, then:

\begin{align*}
& d_{\revise{\DTW}}(x, y)  \nonumber \\
& = \begin{cases}\max (a, b), & m^{\prime}=n^{\prime}=1; \\
a+d_{\revise{\DTW}}(x[a+1, m], y), & m^{\prime}>n^{\prime}=1;  \nonumber\\
\parbox{5.5cm}{$\min \left(a+d_{\revise{\DTW}}(x[a+1, m], y), \right. \\
\left. \quad \quad ~~ b+d_{\revise{\DTW}}(x, y[b+1, n])\right)$} & n^{\prime}>1.\end{cases}
\end{align*}

If $x[1]=y[1]$ and $x[m] \neq y[n]$, then:

\begin{align*}
& d_{\revise{\DTW}}(x, y)  \nonumber \\
& = \begin{cases}a^{\prime}+d_{\revise{\DTW}}\left(x\left[1, m-a^{\prime}\right], y\right), & n^{\prime}=1; \\
\parbox{6.3cm}{$\min \left(a^{\prime}+d_{\revise{\DTW}}\left(x\left[1, m-a^{\prime}\right], y\right), \right. \\
\left. \quad \quad ~~
b^{\prime}+d_{\revise{\DTW}}\left(x, y\left[1, n-b^{\prime}\right]\right)\right)$} & n^{\prime}>1.\end{cases}
\end{align*}

In Theorem <ref>, we call $a, b, a'$ and $b'$ (which are the length of first/last blocks of $x$ or $y$) offsets. Theorem <ref> actually states that, for two sequences $x, y$ with different starting and ending characters, by removing the first/last run of $x$ or $y$, calculating $d_{\revise{\DTW}}(x, y)$ can be reduced to calculating the offset and solving a DTW sub-problem where the sub-sequences start and end with the same character.

To illustrate how we can transfer a DTW problem to an MSS instance, we give a concrete example here.
Let $s = 010110$, $q^{(1)} = 010$, $q^{(2)} = 011$.
We first consider the calculation of the DTW distance between $s$ and $q^{(1)}$.
Since the first and the last blocks of $s$ and $q^{(1)}$ are the same and the number of runs of $s$ is more than that of $q^{(1)}$, we can directly apply Theorem <ref>, where we have the MSS instance $\revise{\MSS}((1, 1, 2), 1)$ and the DTW distance is equal to the solution to this MSS instance.
As for the computation of the DTW distance between $s$ and $q^{(2)}$, we need to first apply Theorem <ref> since the last blocks of $s$ and $q^{(2)}$ are different.
By Theorem <ref>, $d_{\revise{\DTW}}(s, q^{(2)}) = \min (1 + d_{\revise{\DTW}}(\text{``}01011\text{''}, q^{(2)}), 2 + d_{\revise{\DTW}}(s, \text{``}0\text{''}))$.
Then by Theorem <ref>, the calculation of $d_{\revise{\DTW}}(\text{``}01011\text{''}, q^{(2)})$ yields the MSS instance $\revise{\MSS}((1, 1), 1)$ and computing $d_{\revise{\DTW}}(s, \text{``}0\text{''}))$ is equivalent to
$\revise{\MSS}((1, 1, 2), 2)$.

We now show the lower bound on the query complexity using binary queries.

For binary alphabet $\bits$, any algorithm to recover an arbitrary input sequence $s \in \bits^\ell$, where $0 \leq \ell \leq n$, up to equivalence class, by querying the DTW distance to a set of sequences, requires a query complexity of $\Omega(n)$.

We will assume the input sequence is of length $\leq n$ and all the query sequences are of length $\mc{O}(n)$, when the context is clear in the proof.

Given $\revise{\MSS}_1((\underbrace{3, \ldots, 3}_\text{a}, 1, 3, 3, \underbrace{3, \ldots, 3}_\text{b} ), x)$ and $\revise{\MSS}_2((\underbrace{3, \ldots, 3}_\text{a}, 2, 3, 2, \underbrace{3, \ldots, 3}_\text{b} ), x)$, we claim that when $x=1$, $\revise{\MSS}_1 \neq \revise{\MSS}_2$ and when $2 \leq x\leq (a+b+4)/2$, $\revise{\MSS}_1 = \revise{\MSS}_2$.

Proof of claim <ref>.
By the definition of MSS, when $x=1$, $\revise{\MSS}_1 = \min (3, \ldots, 3, 1, 3, 3, 3, \ldots, 3) = 1$ and $\revise{\MSS}_2 = \min (3, \ldots, 3, 2, 3, 2, 3, \ldots, 3) = 2$.
When $2 \leq x < (a+b+4)/2$, $\revise{\MSS}_1 = 3x-2 = \revise{\MSS}_2 $.
When $x = (a+b+4)/2$, if $a$ is odd, $\revise{\MSS}_1 = 3x = \revise{\MSS}_2$; otherwise, $\revise{\MSS}_1 = 3x-2 = \revise{\MSS}_2 $.

Let $\mc{Q}$ be a query set which can distinguish any pair of binary input sequences that-are-distinguishablethat are distinguishable.
For $\forall c \in \mathbb{N}_{+}$ such that $6c+9 \leq n$, $\exists q \in \mc{Q}$ such that #runs($q$) $\in [2c, 2c+6]$.

Proof of claim <ref>.
Consider two input sequences, $s = 01^301^3(0^31^3)^c0$ and $s' = 01^30^21^30^21^3(0^31^3)^{c-1}0$, where $\revise{\len}(s) = \revise{\len}(s') = 6c+9 \leq n$.
We know that #runs($s$) $=$ #runs($s'$) $= 2c+5$.
First we show that $s$ and $s'$ are distinguishable.
Let $q^\dagger = 0(10)^c10$, where #runs($q^\dagger$) $= 2c+3$.
According to Theorem <ref>, $d_{\revise{\DTW}}(s, q^\dagger) = \revise{\MSS}((3, 1, 3, 3, \ldots), 1) = 1$ and $d_{\revise{\DTW}}(s', q^\dagger) = \revise{\MSS}((3, 2, 3, 2, 3, \ldots), 1) = 2$.
Thus, $q^\dagger$ can distinguish $s$ and $s'$.

Next we show, for any query $q$ such that #runs($q$) $\geq 2c+7$ or $\leq 2c-1$, $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$.
Note that, to compute the DTW distances, according to Theorem <ref>, we may remove the first/last blocks of $s$ (and $s'$) or $q$ to reduce to the case of Theorem <ref>.
Since $s$ and $s'$ have the same first and last blocks,
the offsets while reducing to the case of Theorem <ref> are the same. To prove that $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$, we only need to prove that for each possible reduction, the corresponding reduced MSS instances have the same sum of solutions (see Example <ref> for illustration).

To illustrate, take $c=2$ and $q=101$. In this case, we would have $s = 01^301^30^31^30^31^30$, $s' = 01^30^21^30^21^30^31^30$.
According to Theorem <ref>, we have
$d_{\revise{\DTW}}(s, q) = \min (1 + d_{\revise{\DTW}}(s[2, \revise{\len}(s)], q), 1 + d_{\revise{\DTW}}(s, q[2, \revise{\len}(q)])) = \min (1 + d_{\revise{\DTW}}(s[2, 21], q), 1 + d_{\revise{\DTW}}(s, q[2, 3]))$.
Then $d_{\revise{\DTW}}(s[2, 21], q) = \min (1 + d_{\revise{\DTW}}(s[2, 20], q), 1 + d_{\revise{\DTW}}(s[2, 21], q[1, 2]))$.
Also, we note that $d_{\revise{\DTW}}(s, q[2, 3])) = \min (1 + d_{\revise{\DTW}}(s[1, 20], q[2, 3]), 1 + d_{\revise{\DTW}}(s, q[2]))$.

Therefore, to show that $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$, we only need to prove that

$$\begin{cases}d_{\revise{\DTW}}(s[2, 21], q) = d_{\revise{\DTW}}(s'[2, 21], q); \\ d_{\revise{\DTW}}(s[2, 20], q[1, 2]) = d_{\revise{\DTW}}(s'[2, 21], q[1, 2]); \\ d_{\revise{\DTW}}(s[1, 20], q[2, 3]) = d_{\revise{\DTW}}(s'[1, 20], q[2, 3]);\\
d_{\revise{\DTW}}(s, q[2, 3] ) = d_{\revise{\DTW}}(s', q[2, 3] ), \end{cases}$$

where each of the 4 cases corresponds to an MSS instance.

Suppose after applying Theorem <ref>, $s$ and $q$ are reduced to sub-sequences $s^*$ and $q^*$ (where $s^*$ and $q^*$ have the same beginning and ending characters), while $s'$ and $q$ are reduced to $s'^*$ and $q^*$. Now we calculate $d_{\revise{\DTW}}(s^*, q^*)$ and $d_{\revise{\DTW}}(s'^*, q^*)$ according to Theorem <ref>. Suppose $s^*$ and $s'^*$ have $k^*$ runs and $q^*$ have $l^*$ runs.

Case 1. If #runs($q$)$\geq 2c+7 = $#runs($s$)$+2$, then $k^* \leq l^*$, by Theorem <ref> the generated MSS instance only depends on $q^*$ and $k^*$. Thus, $d_{\revise{\DTW}}(s^*, q^*) = d_{\revise{\DTW}}(s'^*, q^*)$.

Case 2. If #runs($q$)$\leq 2c-1$, then $k^* > l^*$ and we have the MSS instances $\revise{\MSS}(s^*, (k^* - l^*)/2)$ and $\revise{\MSS}(s'^*, (k^* - l^*)/2)$. Note that, $(k^* - l^*)/2 \geq (\#\textsc{runs}(s)-\#\textsc{runs}(q)-2)/2 \geq ((2c+5)-(2c-1)-2)/2 = 2$.
By Claim <ref>, we have $\revise{\MSS}(s^*, (k^* - l^*)/2) = \revise{\MSS}(s'^*, (k^* - l^*)/2)$. Thus, $d_{\revise{\DTW}}(s^*, q^*) = d_{\revise{\DTW}}(s'^*, q^*)$.

Combining case 1 and case 2, we know $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$ when #runs($q$) $\geq 2c+7$ or $\leq 2c-1$.
Since there always exists $q\in \mc{Q}$ that can distinguish $s$ and $s'$, we know that #runs($q$) $\in [2c, 2c+6]$, which proves the claim.

Let $c' \in \mathbb{N}_{+}$ satisfy $24 c' -9 \leq n$.
Let $c = 4c' -3$. We have $6c+9 \leq n$.
By Claim <ref>, $\exists q \in \mc{Q}$ such that #runs($q$) $\in [2c, 2c+6]$, i.e., #runs($q$) $\in [8c'-6, 8c']$.
For $c' = 1, 2, \ldots$, intervals  $[8c'-6, 8c']$ are disjoint.
Therefore, there should be at least $\lfloor (n+9)/24 \rfloor = \Omega(n)$ queries in the set $\mc{Q}$.

With these useful results at hand, now we prove the following results for recovering sequences using the DTW distance oracle with only binary queries.

There exists a set $\mc{Q}$ of $2n \in \mc{O}(n)$ queries, each of which has $\mc{O}(n)$ length, such that for any two different input sequences $s$ and $s'$, $s$ and $s'$ are distinguishable $\iff$ $s$ and $s'$ can be distinguished by $\mc{Q}$.

First ($\Leftarrow$), for any given query set $\mc{Q}$ and two different input sequences $s$ and $s'$, if $s$ and $s'$ can be distinguished by $\mc{Q}$ then $s$ and $s'$ are distinguishable.
Then we need to prove the opposite side ($\Rightarrow$).
To see this, we construct the following query set $\mc{Q}$ of size $2n \in \mc{O}(n)$ and prove the contrapositive: if $s$ and $s'$ cannot be distinguished by $\mc{Q}$, then $s$ and $s'$ are not distinguishable.

$$z_i = \begin{cases} 0^{n},\ i = 1; \\ 0^{n}1(01)^{m-1}0^{n} ,\ i = 2m+1; \\ 0^{n}(10)^{m-1}1^{n},\ i = 2m,\end{cases}$$
$$o_i = \begin{cases} 1^{n},\ i = 1; \\ 1^{n}0(10)^{m-1}1^{n} ,\ i = 2m+1; \\ 1^{n}(01)^{m-1}0^{n},\ i = 2m,\end{cases}$$

where $1\leq i \leq n$ and $m$ is an positive integer. It is clear that $o_i$'s and $z_i$'s are of $\mc{O}(n)$ length. Let $\mc{Q} = \{o_i|1\leq i\leq n\}\bigcup\{z_i|1\leq i\leq n\}$. We show that given any two different input sequences $s$ and $s'$, if $s$ and $s'$ cannot be distinguished by $\mc{Q}$ then $s$ and $s'$ are not distinguishable.

Given two different input sequences $s$ and $s'$, if the condensed expressions of $s$ and $s'$ are different, then $s$ and $s'$ can be distinguished by $\mc{Q}$.

Proof of claim <ref>.
We note that the condensed expressions of $o_i$ and $z_i$ for $1 \leq i \leq n$ cover all possible condensed expressions for a sequence with length at most $n$. Therefore, for input sequence $s$, we can find a query sequence $q\in\mc{Q}$ such that $s$ and $q$ have the same condensed expression, and we would have $d_{\revise{\DTW}}(s, q) = 0$.
Since $s$ and $s'$ have different condensed expressions, we would have $d_{\revise{\DTW}}(s', q) \neq 0$. Thus, $q$ distinguishes $s$ and $s'$.

Suppose $s$ and $s'$ cannot be distinguished by $\mc{Q}$. By Claim <ref>, we know that the condensed expression of $s$ and $s'$ are the same. Let the number of runs in $s$ and $s'$ be $k = \#\textsc{runs}(s) = \#\textsc{runs}(s')$.

If $s$ and $s'$ cannot be distinguished by $\mc{Q}$, then $k\geq 3$.

Proof of claim <ref>.
Consider the query sequence $z_1 = 0^n$ and $o_1 = 1^n$.
By querying $z_1$ and $o_1$, we can obtain the number of 1's and 0's in the input sequence. If $k \leq 2$, then $s$ (and $s'$) would contain at most a single $0$-run and a $1$-run. With queries $z_1$ and $o_1$ we can determine the length of the $0$-run and the $1$-run in $s$ and $s'$, and therefore distinguish them.

If $s$ and $s'$ cannot be distinguished by $\mc{Q}$, then $\textsc{lor}(s, 1) = \textsc{lor}(s', 1)$ and $\textsc{lor}(s, k) = \textsc{lor}(s', k)$.

Proof of claim <ref>. If $s$ and $s'$ start with $0$, we show that $d_{\revise{\DTW}}(s, o_{k-1}) = \textsc{lor}(s, 1) $.
Since $k\geq 3$, by Theorem <ref>,

\begin{align*}
\intertext{$d_{\DTW}(s, o_{k-1})=$}
\min \left(d_{\DTW}(s[\textsc{lor}(s, 1) +1, \len(s)], o_{k-1})+\textsc{lor}(s, 1), \right.\\
\left. n+d_{\DTW}(s, o_{k-1}[n+1, \len(o_{k-1})])\right)   \nonumber
\end{align*}

\begin{align*}
d_{\revise{\DTW}}(s, o_{k-1}) = \min \left(\textsc{lor}(s, 1) +d_{\revise{\DTW}}(s[\textsc{lor}(s, 1) +1, \revise{\len}(s)], o_{k-1}), \right. \\
\left. n+d_{\revise{\DTW}}(s, o_{k-1}[n+1, \revise{\len}(o_{k-1})])\right)   \nonumber
\end{align*}

Note that $d_{\revise{\DTW}}(s[\textsc{lor}(s, 1) +1, \revise{\len}(s)], o_{k-1}) = 0$, and $\textsc{lor}(s, 1)  \leq n \leq n+d_{\revise{\DTW}}(s, o_{k-1}[n+1, \revise{\len}(o_{k-1})])$, we know that $d_{\revise{\DTW}}(s, o_{k-1}) = \textsc{lor}(s, 1) $. Similarly $d_{\revise{\DTW}}(s', o_{k-1}) = \textsc{lor}(s', 1)$.
Since $s$ and $s'$ cannot be distinguished by $\mc{Q}$, we have $\textsc{lor}(s, 1)  = d_{\revise{\DTW}}(s, o_{k-1}) = d_{\revise{\DTW}}(s', o_{k-1}) = \textsc{lor}(s', 1) $. Similarly, we would have $\textsc{lor}(s, k)  = d_{\revise{\DTW}}(s, z_{k-1}) = d_{\revise{\DTW}}(s', z_{k-1}) = \textsc{lor}(s', k) $.

By symmetry, if $s$ and $s'$ starts with $1$, we would have  $\textsc{lor}(s, 1)  = d_{\revise{\DTW}}(s, z_{k-1}) = d_{\revise{\DTW}}(s', z_{k-1}) = \textsc{lor}(s', 1) $ and  $\textsc{lor}(s, k)  = d_{\revise{\DTW}}(s, o_{k-1}) = d_{\revise{\DTW}}(s', o_{k-1}) = \textsc{lor}(s', k) $. This finishes the proof for Claim <ref>.

Next, we show that $s$ and $s'$ cannot be distinguished by any binary query $r$. Let the number of runs in $r$ be $l = \#\textsc{runs}(r)$.
Given $s$ and $r$, we can calculate $d_{\revise{\DTW}}(s, r)$ with Theorem <ref> and Theorem <ref>. Note that in Theorem <ref>, we may remove the first/last blocks of $s$ (and $s'$) or $r$ to reduce to the case of Theorem <ref>. By Claim <ref> we have $\textsc{lor}(s, 1)  = \textsc{lor}(s', 1) $ and $\textsc{lor}(s, k)  = \textsc{lor}(s', k) $, while $\textsc{lor}(r, 1) $ and $\textsc{lor}(r, l) $ are only related to $r$ but not $s$ and $s'$. Therefore,
the offsets while reducing to the case of Theorem <ref> are the same. To prove that $d_{\revise{\DTW}}(s, r) = d_{\revise{\DTW}}(s', r)$, we only need to prove that for each possible reduction, the corresponding reduced MSS instances have the same sum of solutions (see Example <ref> for illustration).

To illustrate, take $s = 010110$, $s' = 011010$ and $r = 1001011$ as an example. In this case, we would have $\textsc{lor}(s, 1)  = \textsc{lor}(s', 1)  = 1$, $\textsc{lor}(s, k)  = \textsc{lor}(s', k)  = 1$, $\textsc{lor}(r, 1)  = 1$ and $\textsc{lor}(r, l)  = 2$.
According to Theorem <ref>, we have
$d_{\revise{\DTW}}(s, r) = \min (\textsc{lor}(s, 1)  + d_{\revise{\DTW}}(s[\textsc{lor}(s, 1) +1, \revise{\len}(s)], r), \textsc{lor}(r, 1)  + d_{\revise{\DTW}}(s, r[\textsc{lor}(r, 1) +1, \revise{\len}(r)])) = \min (1 + d_{\revise{\DTW}}(s[2, 6], r), 1 + d_{\revise{\DTW}}(s, \\r[2, 7]))$.
Then $d_{\revise{\DTW}}(s[2, 6], r) = \min (\textsc{lor}(s, k)  + d_{\revise{\DTW}}(s[2, 6-\textsc{lor}(s, k) ], r), \textsc{lor}(r, l)  + d_{\revise{\DTW}}(s[2, 6], \\r[1, \revise{\len}(r)-\textsc{lor}(r, l) ])) = \min (1 + d_{\revise{\DTW}}(s[2, 5], r), 2 + d_{\revise{\DTW}}(s[2, 6], r[1, 5]))$.
Also, $d_{\revise{\DTW}}(s, r[2, 7])) = \min (\textsc{lor}(s, k)  + d_{\revise{\DTW}}(s[1, \revise{\len}(s)-\textsc{lor}(s, k) ], r[2, 7]), \textsc{lor}(r, k)  + d_{\revise{\DTW}}(s, r[2, 7-\textsc{lor}(r, k) ] )) = \min (1 + d_{\revise{\DTW}}(s[1, 5], r[2, 7]), 2 + d_{\revise{\DTW}}(s, r[2, 5] ))$.

Therefore, to show that $d_{\revise{\DTW}}(s, r) = d_{\revise{\DTW}}(s', r)$, we only need to prove that

$$\begin{cases}d_{\revise{\DTW}}(s[2, 5], r) = d_{\revise{\DTW}}(s'[2, 5], r); \\ d_{\revise{\DTW}}(s[2, 6], r[1, 5]) = d_{\revise{\DTW}}(s'[2, 6], r[1, 5]); \\ d_{\revise{\DTW}}(s[1, 5], r[2, 7]) = d_{\revise{\DTW}}(s'[1, 5], r[2, 7]);\\
d_{\revise{\DTW}}(s, r[2, 5] ) = d_{\revise{\DTW}}(s', r[2, 5] ), \end{cases}$$

where each of the 4 cases corresponds to an MSS instance.

Suppose after applying Theorem <ref>, $s$ and $r$ are reduced to sub-sequences $s^*$ and $r^*$ (where $s^*$ and $r^*$ have the same beginning and ending characters), while $s'$ and $r$ are reduced to $s'^*$ and $r^*$. Now we calculate $d_{\revise{\DTW}}(s^*, r^*)$ and $d_{\revise{\DTW}}(s'^*, r^*)$ according to Theorem <ref>. Suppose $s^*$ and $s'^*$ have $k^*$ runs and $r^*$ have $l^*$ runs.

Case 1. If $k^* = l^*$, then $d_{\revise{\DTW}}(s^*, r^*) = d_{\revise{\DTW}}(s'^*, r^*) = 0$.

Case 2. If $k^* < l^*$, by Theorem <ref> the generated MSS instance only depends on $r^*$ and $k^*$. Thus, $d_{\revise{\DTW}}(s^*, r^*) = d_{\revise{\DTW}}(s'^*, r^*)$.

Case 3. If $k^* > l^*$, we have the MSS instances $\revise{\MSS}(s^*, (k^* - l^*)/2)$ and $\revise{\MSS}(s'^*, (k^* - l^*)/2)$. Note that, we can always find a query $q \in \mc{Q}$ which has $l^*$ runs and has the same starting and ending characters as $s^*$ and $s'^*$. Consider $d_{\revise{\DTW}}(s, q)$ and $d_{\revise{\DTW}}(s', q)$. Note that the first and last runs of $q$ are both of length $n$ and removing them would yield at least cost $n$, the only possible reduction would be $d_{\revise{\DTW}}(s^*, q)$ and $d_{\revise{\DTW}}(s'^*, q)$. Since $q$ cannot distinguish $s$ and $s'$, we have $d_{\revise{\DTW}}(s, q) = d_{\revise{\DTW}}(s', q)$, so $d_{\revise{\DTW}}(s^*, q) = d_{\revise{\DTW}}(s'^*, q)$, implying that $\revise{\MSS}(q^*, (k^* - l^*)/2)$ and $\revise{\MSS}(q'^*, (k^* - l^*)/2)$ have the same sum of solution. Therefore, $d_{\revise{\DTW}}(s^*, r^*) = d_{\revise{\DTW}}(s'^*, r^*)$.

Combining the 3 cases above, we always have $d_{\revise{\DTW}}(s^*, r^*) = d_{\revise{\DTW}}(s'^*, r^*)$, so $d_{\revise{\DTW}}(s, r) = d_{\revise{\DTW}}(s', r)$, implying that $s$ and $s'$ cannot be distinguished by $r$. This finishes the proof for Theorem <ref>.

§.§ Exact Recovery with Extra Character(s)

For a binary alphabet $\bits$, any algorithm to recover arbitrary input sequence $s \in \bits^\ell$ where $0 \leq \ell \leq n$ by querying DTW distance to a set of sequences of length $\mc{O}(n)$ constant-sized-alphabetfrom a constant-sized extended alphabet $\Sigma$ would require a query complexity of $\Omega(n/\log n)$.

upper-or-lowerTheorem <ref> shows the lower bound of the query complexity for DTW exact recovery.
The proof of Theorem <ref> is given by an information-theoretic lower bound, which refers back to the proof of Theorem <ref>.

With this lower bound, now we would like to show that if one is allowed to construct queries from a slightly larger alphabet beyond $\bits$, there exists a non-adaptive query strategy such that this lower bound is attainable as per the order of magnitude.

§.§.§ With One Extra Character

For a binary alphabet $\bits$ and an input sequence $s := \bits^{\ell}$ where $0 \leq \ell \leq n$, there exists an algorithm to recover the input sequence $s$, given $n^2+n \in \mc{O}(n^2)$ query sequences $\revise{\mc{Q}}$ and the $d_{\revise{\DTW}}(s, q)$ to each query sequence $q \in \revise{\mc{Q}}$, where the query sequences are allowed to use only one extra character.

Proof of Theorem <ref>
We give our proof by constructing $n^2+n$ query sequences of length $\leq n$ and presenting an algorithm to recover an input sequence $s$ from its DTW distance to these 1-extra-char$n^2+n$ query sequences.

Let $z_{i,k} = \begin{cases}0(10)^{m}(\frac{1}{2})^{k}, i = 2m+1; \\ (01)^{m}(\frac{1}{2})^{k}, i = 2m,\end{cases}$ and $o_{i,k} = \begin{cases}1(01)^{m}(\frac{1}{2})^{k}, i = 2m+1; \\ (10)^{m}(\frac{1}{2})^{k}, i = 2m,\end{cases}$ where $m$ is a non-negative integer, $1 \leq i \leq n$ and $0\leq k \leq n-i$. Let $\mc{Q} = \{o_{i,k}|1\leq i\leq n, 0\leq k \leq n-i\}\bigcup\{z_{i, k}|1\leq i\leq n, 0\leq k \leq n-i\} $. We have $|\mc{Q}| = 2\sum_{i = 1}^{n}i = n^2 + n$.

Without loss of generality, we can assume that $s$ starts with a $0$ and has $t$ runs, where the $i$-th run of $s$ is $\textsc{lor}(s, i) $, $l = \sum_{i = 1}^{t}\textsc{lor}(s, i) $. Then $d_{\revise{\DTW}}(z_{t, 0}, s) = 0$.  Consider $d_{\revise{\DTW}}(z_{i, k}, s)$ where $1\leq i \leq t$. The first $i$ runs of $s$ have a total length of $\sum_{j=1}^{i}\textsc{lor}(s, j) $, and the last $t-i$ runs of $s$ have a total length of $\sum_{j=i+1}^{t}\textsc{lor}(s, j) $.

For $1\leq i\leq t$, $d_{\revise{\DTW}}(z_{i, k}, s) = \frac{k}{2} \iff k\geq \sum_{j=i+1}^{t}\textsc{lor}(s, j) $.

Proof of Claim <ref>. Since each $\frac{1}{2}$ in $z_{i, k}$ corresponds to at least $\frac{1}{2}$ cost, we have $d_{\revise{\DTW}}(z_{i, k}, s) \geq \frac{k}{2}$. Note that $s[1, \sum_{j=1}^{i}\textsc{lor}(s, j) ]$ and $z_{i, k}[1, i]$ can be perfectly matched. If $k\geq \sum_{j=i+1}^{t}\textsc{lor}(s, j) $, then $s[(\sum_{j=1}^{i}\textsc{lor}(s, j) )+1, l]$ and $z_{i, k}[i+1, i+k] = (\frac{1}{2})^{k}$ can be matched with exactly $\frac{k}{2}$ cost, so $d_{\revise{\DTW}}(z_{i, k}, s) = \frac{k}{2}$. Otherwise, if $k< \sum_{j=i+1}^{t}\textsc{lor}(s, j) $, we show that $d_{\revise{\DTW}}(z_{i, k}, s) > \frac{k}{2}$. In fact, if any of the $\frac{1}{2}$ in $z_{i, k}$ is matched to more than one character in $s$, we would already have $d_{\revise{\DTW}}(z_{i, k}, s) > \frac{k}{2}$. If all $\frac{1}{2}$'s in $z_{i, k}$ have degree 1, then $z_{i, k}[1..i]$ must be matched with $s[1, l-k]$. Since $l-k >  \sum_{j=1}^{i}\textsc{lor}(s, j) $, $z_{i, k}[1..i]$ and $s[1, l-k]$ cannot be perfectly matched, yielding a non-zero cost. This finishes the proof of Claim <ref>.

By Claim <ref>, we know that for $1\leq i \leq t$, $\sum_{j=i+1}^{t}\textsc{lor}(s, j)  = min_{d_{\revise{\DTW}}(z_{i, k}, s) = \frac{k}{2}}k$. In this way, we can recover the length of each run in $s$, and therefore recover $s$. A similar analysis can be performed for the cases where $s$ starts with a single $1$. $\blacksquare$

§.§.§ With Two Extra Characters

For a binary alphabet $\bits$ and an input sequence $s := \bits^{\ell}$ where $0 \leq \ell \leq n$, there exists an algorithm to recover the input sequence $s$, given $n + 2 \in \mc{O}(n)$ query sequences $\revise{\mc{Q}}$ of length $\leq n$ and the $d_{\revise{\DTW}}(s, q)$ to each query sequence $q \in \revise{\mc{Q}}$, where the query sequences are allowed to use only $\mc{O}(1)$ extra characters.

Optimal re-matching (hybrid stitching) when both query and input sequences have a vertex with degree greater than $1$ (c.f. Claim <ref>).

Proof of Theorem <ref>.
We give our proof by constructing $n+2 \in \mc{O}(n)$ query sequences of length $\leq n$ and presenting an algorithm to recover an input sequence $s$ from its DTW distance to these $n+2$ query sequences.

Note that for any sequence $s$, we have $d_{\revise{\DTW}}(s, 0) = 0 \iff s \text{ consists of only 0's}$ and $d_{\revise{\DTW}}(s, 1) = 0 \iff s \text{ consists of only 1's}$. We can also derive that $d_{\revise{\DTW}}(0^m, 1) = m$ and $d_{\revise{\DTW}}(1^m,0) = m$. Thus, any input sequence consisting of only $0$s or $1$s can be exactly recovered
by the two query sequences $0$ and $1$.
For simplicity, we assume in the rest of the proof that the input sequence $s$ contains both $0$ and $1$ and let $s = s[1]s[2] \ldots s[\ell]$.

Query Sequences Construction.
Let $a, b$ be two fractional characters that satisfy $0 < b-a < a < b < \frac{1}{2}$ and the denominators of $a, b$ are co-prime.
We will use $a, b$ as the extra characters to construct the query sequences.
In particular, the rest of the query sequences (other than the $0$ query and the $1$ query) consist of queries $\mc{Q}$ is in the form of $a^{n-i}b^{i}$, where $i = 1, \dots, n$.
It is not hard to see this set of queries are monotonic sequences, for which we show the following property holds in the distance query to DTW.
wlog-1We will use $a = \frac{1}{3}$ and $b = \frac{2}{5}$ as a running example for better explanation when necessary, but the proof works for all $a, b$ satisfying the condition.

Given a monotonic sequence $q$ of length $n$ where

\begin{equation}
\min_{i\in [n]}\max\{|q[i]-0|, |q[i]-1|\} > \max_{i,j\in [n]}|q[i]-q[j]|,\label{equ:single_direction_o1}
\end{equation}

for any input sequence $s$ with length $\ell \leq n$, given a DTW matching $M$ for $(q,s)$, we have $\revise{\deg}(q[i]) = 1$ for all elements $q[i]$ in $q$.

Suppose $\exists i\in[\ell]$ such that $\revise{\deg}(q[i]) > 1$.
We first prove the following two claims.

For any edge $e$ in $M$, the two vertices corresponding to $e$ in $M$ cannot have degree $>1$ at the same time.

Proof of Claim <ref>. This is trivial, since otherwise by deleting $e$ we would obtain a better matching.

There does not exist $i\in[n]$ and $j\in[\ell]$ such that $\revise{\deg}(q[i])>1$ and $\revise{\deg}(s[j])>1$.

Proof of Claim <ref>. We prove this by contradiction. Suppose $\exists(i,j)$ where $i\in[n]$ and $j\in[\ell]$ such that  $\revise{\deg}(q[i])>1$ and $\revise{\deg}(s[j])>1$.
index_setConsider the following index sets $\mb{X}, \mb{Y}, \mb{Z}$.
Let $\mb{X} = \{x \in [n] \mid \revise{\deg}(q[x]) > 1\}$, $\mb{Y} = \{y \in [\ell] \mid \revise{\deg}(s[y]) > 1 \}$ and $\mb{Z} = \{z \in [\ell] \mid \exists x \in \mb{X} \text{ such that edge }(q[x], s[z])\in M\}$. According to Claim <ref>, we know that $\mb{Y}\bigcap \mb{Z} = \emptyset$. Let $d = \min_{y\in \mb{Y}, z\in \mb{Z}}|y-z|$, we would have $d>0$. Suppose we have $x_0\in \mb{X}, y_0\in \mb{Y}, z_0\in \mb{Z}$ such that edge $(q[x_0], s[z_0])\in M$ and $|y_0-z_0| = d$.
And this leaves two cases to discuss.

1) if $y_0 < z_0$, then we know that (i) $\forall k\in (y_0,z_0)$, $\revise{\deg}(s[k]) = 1$; otherwise we would have $k\in \mb{Y}$ and $|k-z_0|<d$, causing a contradiction. (ii) $\forall k_1, k_2$ within range $(y_0, z_0)$, $k_1\neq k_2$, we would have $s[k_1]$ and $s[k_2]$ matched to different vertices in $q$; otherwise, suppose edges $(q[t], s[k_1])\in M$ and $(q[t], s[k_2])\in M$. We would have $t\in \mb{X}$, $k_1\in \mb{Z}$ and $|y_0-k_1| < d$, causing a contradiction.

Now, since $d$ is minimal, we can suppose that $s[y_0]$ is matched to
$$\{q[w-\revise{\deg}(s[y_0])+1], q[w-\revise{\deg}(s[y_0])+2], \ldots, q[w]\},$$
and $q[x_0]$ is matched to
$$\{s[z_0], s[z_0+1], \ldots, s[z_0+\revise{\deg}(q[x_0])-1]\}.$$

Since $y_0 < z_0$, by the monotonic property of the matching, we know that $w < x_0$.
With (i) and (ii), we know that for $w < l < x_0$ and $y_0 < r < z_0$, the vertices $q[l]$'s and $s[r]$'s are perfectly matched one-to-one. Fig <ref> is an illustration of such an example.

We now claim, by re-matching edges between vertices $q[w], q[w+1], \ldots, q[x_0]$ and $s[y_0], s[y_0+1], \ldots, s[z_0]$, we can construct another matching $M'$ which is better than $M$, contradicting that $M$ is a DTW matching. We remove the $d+1$ edges $E = \{(q[w], s[y_0]), (q[w+1], s[y_0+1]), \ldots, (q[x_0], s[z_0])\}$ from $M$ and add $d$ new edges $E'=\{(q[w], s[y_0+1]), (q[w+1], s[y_0+2]), \ldots , (q[x_0-1], s[z_0])\}$ to obtain a new matching $M'$. Since $\revise{\deg}(s[y_0])>1$ and $\revise{\deg}(q[x_0])>1$ in $M$, $M'$ would still be a valid matching. Computing the sum of two sets of edges $E$ and $E'$, respectively, would yield
the following.
Equation. <ref> (see the cross-column equations).

\begin{align*}
\Cost(E)  &   = |s[y_0]-q[w]|+\sum_{i = 1}^{d}|s[y_0+i]-q[w+i]| \label{eqn_dbl_1}\\
& > |q[w]-q[x_0]|+ \sum_{i = 1}^{d}|s[y_0+i]-q[w+i]| \hfill \tag{Equation.~\ref{equ:single_direction_o1}} \\
& = \sum_{i = 1}^{d}|q[w+i-1]-q[w+i]|+ \sum_{i = 1}^{d}|s[y_0+i]-q[w+i]|  \hfill \tag{Monotonicity of $q$}  \\
& =  \sum_{i = 1}^{d}(|q[w+i-1]-q[w+i]|+|s[y_0+i]-q[w+i]|) \nonumber \\
& \geq \sum_{i = 1}^{d}|q[w+i-1]-s[y_0+i]| \hfill \tag{Triangle Inequality}\\
& = \revise{\Cost}(E'). \nonumber
\end{align*}

\begin{align}
\Cost(E)  &   = |s[y_0]-q[w]|+\sum_{i = 1}^{d}|s[y_0+i]-q[w+i]| \label{eqn_dbl_1}\\
& > |q[w]-q[x_0]|+ \sum_{i = 1}^{d}|s[y_0+i]-q[w+i]| \hfill \tag{Equation.~\ref{equ:single_direction_o1}} \\
& = \sum_{i = 1}^{d}|q[w+i-1]-q[w+i]|+ \sum_{i = 1}^{d}|s[y_0+i]-q[w+i]|  \hfill \tag{Monotonicity of $q$}  \\
& =  \sum_{i = 1}^{d}(|q[w+i-1]-q[w+i]|+|s[y_0+i]-q[w+i]|) \nonumber \\
& \geq \sum_{i = 1}^{d}|q[w+i-1]-s[y_0+i]| \hfill \tag{Triangle Inequality}\\
& = \revise{\Cost}(E'). \nonumber
\end{align}

So $M'$ would be a better matching than $M$, causing a contradiction.

2) if $y_0 > z_0$, this case is symmetric to 1) and we can use a similar method to complete the proof by contradiction. We give a detailed proof in the appendix.

Combining the two cases finishes the proof for Claim <ref>.

Suppose $\exists i\in[\ell]$ such that $\revise{\deg}(q[i]) > 1$. With Claim 2, we know that $\forall j\in[\ell]$, $\revise{\deg}(s[j]) = 1$. Thus, we would have $\sum_{j=1}^{\ell}\revise{\deg}(s[j]) = \sum_{i=1}^{n}\revise{\deg}(q[i]) > n \geq \ell = \sum_{j=1}^{\ell}\revise{\deg}(s[j]),$
which causes a contradiction and finishes the proof of Lemma <ref>.

Obtaining a lower cost matching by shifting matched edges (c.f. Lemma <ref>).

Furthermore, we have the following lemma for the DTW matching for our query sequences.

For any given input sequence $s$ and query $q \in \mc{Q}$, the DTW matching $M$ for $(q, s)$ has $\revise{\deg}(s[i]) = 1$ in $M$ if $s[i]=1$.

We give proof by contradiction. Given an optimal DTW matching $M$ for $(q,s)$, suppose $\exists 1\leq i\leq \ell$ such that $s[i] = 1$ and $\revise{\deg}(s[i]) > 1$. Suppose $s[i]$ is matched to $q[j], q[j+1], \ldots, q[j+\revise{\deg}(s[i])-1]$.

First, we show that we can “swap” $s[i]$ with its neighboring element while maintaining the optimality of the matching. If one of the neighboring elements of $s[i]$ is $1$, w.l.o.g, suppose $s[i+1] = 1$, then we can construct an alternate optimal matching $M^{*}$ where $\revise{\deg}(s[i]) = 1$ and $\revise{\deg}(s[i+1])>1$. According to Lemma <ref>, $s[i+1]$ cannot be matched with any of $q[j], q[j+1], \ldots, q[j+\revise{\deg}(s[i])-1]$ in $M$, otherwise there would exist $j+1\leq k\leq j+\revise{\deg}(s[i])-1$ such that $\revise{\deg}(q[k]) = 2$. Thus, by matching $q[j+1], \ldots, q[j+\revise{\deg}(s[i])-1]$ to $s[i+1]$ instead of $s[i]$, we would obtain a new optimal matching $M^{*}$ where $\revise{\deg}(s[i]) = 1$ and $\revise{\deg}(s[i+1])>1$.

As there exists at least one $0$ in $s$, we know that there exists an optimal DTW matching $M_0^{*}$ for $(q, s)$ where $\exists s[i]$ such that $s[i] = 1$, $\revise{\deg}(s[i]) > 1$ and one of the neighboring element of $s[i]$ is $0$. Without loss of generality, suppose $s[i+1] = 0$. Similarly, according to Lemma <ref>, $s[i+1]$ cannot be matched with any of $q[j], q[j+1], \ldots, q[j+\revise{\deg}(s[i])-1]$ in $M_0$. Here we construct a new matching $M_0'$ by matching $q[j+1], \ldots , q[j+\revise{\deg}(s[i])-1]$ to $s[i+1]$ instead of $s[i]$. Fig <ref> illustrates an example of such a construction. Considering the total cost of differing edges in both matchings, we have
> \sum_{k=j+1}^{j+\revise{\deg}(s[i])-1}\frac{1}{2}
> \sum_{k=j+1}^{j+\revise{\deg}(s[i])-1}|s[i+1]-q[k]|.$
Thus $M_0^*$ would be a better matching than $M_0$, causing a  contradiction and thus finishing the proof.

Notation clarification.
For the rest of the proof, we will use $q^{(i)}$ to denote the $i$-th query in the query set $\mc{Q}$ and $q^{(i)}[j]$ the $j$-th character in $q^{(i)}$.

For any input sequence $s$, there exists isomorphic_set-0a set of isomorphic matchings $\mc{M}^*$, where $\revise{M_i^*(q^{(i)}, s)} \in \mc{M}^*$ is optimal for query $q^{(i)} \in \mc{Q}$.

According to previous assumptions, we know that the input sequence $s$ contains at least one $0$. Suppose $s[u]$ is the first $0$ in $s$.
We construct the following matching $M_i^*$ for each $q^{(i)} \in \mc{Q}$:

1) For $1\leq j < u$, $q^{(i)}[j]$ is matched to $s[j]$ in $M_i^*$;

2) For $u\leq j \leq u+n-\ell$, $q^{(i)}[j]$ is matched to $s[u]$ in $M_i^*$;

3) For $ u+n-\ell < j \leq n$, $q^{(i)}[j]$ is matched to $s[j-(n-\ell)]$ in $M_{i}^*$.

The constructed $M_i^*$'s form isomorphic_set-1a set of isomorphic matchings, and we will show that each $M_i^*$ is an optimal matching between $s$ and $q^{(i)}$. To prove this, we first define the “shifting” operation.

Given a matching $M$ between input sequence $s$ of length $\ell$ and query sequence $q\in\mc{Q}$ of length $n$. Suppose $\exists 1\leq x < y \leq \ell$ s.t. $s[x] = s[y] = 0$, $\revise{\deg}(s[x]) > 1$, and $\forall x < j < y$, $\revise{\deg}(s[j]) = 1$. We now construct a new matching $M'$ based on $M$:

Suppose $q[z]$ is the last character matched to $s[x]$ and $q[w]$ is the first character matched to $s[y]$, we know that $z-x = w-y$ (cf. lemma <ref>). For $x \leq j < y$, we remove the edge $(q[j-x+z], s[j])$ from $M$ and add the edge $(q[j-x+z], s[j+1])$. As $\revise{\deg}(s[x]) > 1$. This will give us a valid matching.
We call this process a shifting operation.

An illustration of the shifting operation (c.f. Definition <ref>).

An illustration of the shifting operation is shown in Fig <ref>.
The shifting operation reduces $\revise{\deg}(s[x])$ by 1 and increases $\revise{\deg}(s[y])$ by 1, while preserving the degree of all other vertices in $s$.
Now we give the following claims for shifting operations.

A shifting operation does not reduce the total cost of the matching.

Proof of claim.
As one can observe, the shifting operation will not increase the total number of edges – the number of removed edges is equal to the number of newly added edges.
Then we only need to consider the cost of those changed edges.
wlog-2Recall that our monotonic query sequences are in the form of $a^{n-k}b^{k}$ for $k = 1, \dots, n$.
To calculate the change of cost in the shifting operation, we have two cases to analyze.

Case 1. All characters between $q[z]$ and $q[w]$ (including $q[z]$ and $q[w]$) in the query sequence are the same, either $a$ or $b$.
In this case, the total cost does not change after the shifting operation.
This is because, $\forall s[j] \in s$ s.t. $x < j < y$, the edge changes from $(q[j-x+z], s[j])$ to $(q[j-x+z-1], s[j])$ and the cost $\revise{\Cost}(q[j-x+z], s[j]) = \revise{\Cost}(q[j-x+z-1], s[j])$ since $q[j-x+z] = q[j-x+z-1]$.
Notice in the matching before shifting, we have the edge $(q[z], s[x])$ while in the matching after shifting this edge is removed but the edge $(q[w], s[y])$ is added.
These two edges have equal cost $\revise{\Cost}(q[z], s[x]) = \revise{\Cost}(q[w], s[y])$ because $s_x = s_y = 0$.

Case 2. The characters between $q[z]$ and $q[w]$ (including $q[z]$ and $q[w]$) contain both $a$ and $b$.
Without loss of generality, we can assume there exists qi_iindex $i$, s.t. for $j < i, q[j] = a$ while for $j \geq i, q[j] = b$.
Applying a similar analysis as we did in case 1, the cost of edges containing characters $q[j]$ such that $z < j < i - 1$ and_oror $i< j < w$ remains the same after the shifting operation.
Suppose $s[t]$ gets matched to $q[i]$ before the shifting operation.
We only need to analyze the cost of the (removed and added) edges corresponding to characters $s[x], s[t]$ and $s[y]$.
Before the shifting operation, these three characters get matched in edges $(q[z], s[x]), (q[i], s[t])$, respectively, while in the matching after shifting, they are involved in edges $(q[i-1], s[t]), (q[w-1], s[y])$.
We can compute the total cost of these three edges before shifting $\revise{\Cost_{\text{before}}} = |a - 0| + |b - s[t]|$ and the total cost after shifting $\revise{\Cost_{\text{after}}} = |a - s[t]| + |b - 0|$.
If $s[t] = 0$, then $\revise{\Cost_{\text{before}}} = a+b = \revise{\Cost_{\text{after}}}$; otherwise if $s[t] = 1$, then $\revise{\Cost_{\text{before}}} = a + 1 - b$ and $\revise{\Cost_{\text{after}}} = 1 - a  + b$.
Since $0 < a < b < 1$, $\revise{\Cost_{\text{before}}} < \revise{\Cost_{\text{after}}}$ when $s[t] = 1$.
Therefore in this case, $\revise{\Cost_{\text{before}}} \leq \revise{\Cost_{\text{after}}}$.

Combining both cases, the total cost of the matching before the shifting operation could be only less than or equal to the cost after shifting, which proves the claim.

Given input sequence $s$, query $q^{(i)}\in \mc{Q}$ and any matching $M_i$ between $s$ and $q^{(i)}$.
If $M_i$ satisfies the properties that (i) $\forall 1\leq j \leq \ell$, $\revise{\deg}(s[j]) > 1\Rightarrow s_j = 0$, (ii) $\forall 1 \leq k \leq n$, $\revise{\deg}(q^{(i)}[k])=1$, then we can obtain $M_i$ by applying a series of shifting operations to $M_i^*$.

Proof of Claim.
If the input sequence $s$ contains only a single 0, then this claim is trivial since any matching $M_i = M_i^*$.
For cases that the input sequence $s$ contains more than one 0, without loss of generality, we can assume $s$ has $k$ 0's and in the matching $M_i$, for each 0 in $s$ (denoted by $s_{0_m}$, $m \in [k]$), the degree $\revise{\deg}(s_{0_m}) = t_m \geq 1$.
Note that, as we defined, the shifting operation can be performed between $s[x]$ and $s[y]$, if $s[x] = s[y] = 0$, $\revise{\deg}(s[x]) > 1$, and $\forall x < t < y$, $\revise{\deg}(s[t]) = 1$.
This condition obviously holds for the matching $M_i^*$ if $s[x]$ and $s[y]$ are the nearest neighboring 0's in the input sequence $s$, because all characters between $s[x]$ and $s[y]$ are 1's and in $M_i^*$ all characters $s[j]$ s.t. $s[j] = 1$ we have $\revise{\deg}(s[j]) = 1$ (indicated by Lemma <ref>).
Property (ii) indicates that both $M_i^*$ and $M_i$ have the same number of edges $n$, and property (i) indicates $\forall 1 \leq j \leq \ell, s[j] = 1 \Rightarrow  \revise{\deg}(s[j])=1$.
For $M_i^*$ and $M_i$, we have $\sum_{s[j]=0} \revise{\deg}(s[j]) = n - (\# 1$s in $s) = \sum_{m=1}^k t_m$.
For matching $M_i^*$, the degree of all 0's is 1 except for the first 0 and therefore the degree of the first 0 is $\sum_{m=1}^k t_m - (k - 1)$.
Therefore, we can perform the shifting operation $\sum_{m=1}^k t_m - (k - 1) - t_1$ times to move $\sum_{m=1}^k t_m - (k - 1) - t_1$ edges from the first 0 to the second 0.
Similarly, we continue doing shifting operations to move $\sum_{m=j}^{k} t_m - (k - 1) - t_j$ edges from the $j$-th 0 to the $(j+1)$-th 0.
We can hence obtain $M_i$ after all shifting operations are finished and this shows the correctness of this claim.

Suppose $M_{i0}$ is an optimal DTW matching between $s$ and $q^{(i)}$.
By Lemma <ref>, in DTW matching $M_{i0}$, $\forall 1 \leq k \leq n, \revise{\deg}(q^{(i)}[k]) = 1$.
By Lemma <ref> we know that $M_{i0}$ has $\revise{\deg}(s[i]) = 1$ in $M_{i0}$ if $s[i] = 1$, so $\forall 1\leq j \leq \ell$, $\revise{\deg}(s[j]) > 1\Rightarrow s_j = 0$ in $M_{i0}$. By Claim <ref> we know that we can obtain $M_{i0}$ by applying a series of shifting operations to $M_i^*$, and according to Claim <ref> we would have $\revise{\Cost}(M_i^*)\leq \revise{\Cost}(M_{i0})$. Thus, $M_i^*$ is an optimal matching between $q^{(i)}$ and $s$.

Let $x_j \in\{0, 1\}$ be the value of the character matched to $q^{(i)}[j]$ in all isomorphic DTW matchings $M_i^*$, where $j \in [n]$.
We denote the sequence $x \coloneqq x[1]\dots x[n]$, where $x[j] = x_j$ for $j \in [n]$.
amplify_leftmost_0The sequence $x$ can be obtained by amplifying the leftmost 0 in s.

We see the proposition is naturally true based on the construction of $M_i^*$ in the proof of Lemma <ref>.

Algorithm to recover DTW matching $M_i^*$.
star_unstar_2 We now give the algorithm to recover the isomorphic DTW matchings $M_i^*$ with the query set $\mc{Q}$ (Algorithm <ref>: line 8-15).
The query result $d_i$ of $q^{(i)} = a^{n-i}b^i$ would be $d_i = \sum_{j=1}^{n-i} |x[j]-a|+\sum_{j=n-i+1}^{n}|x[j]-b|$.
Recall that $a = \frac{1}{3}$ and $b = \frac{2}{5}$.
Consider $q^{1} = a^{n-1} b$, where $d_1 = \sum_{j=1}^{n-1} |x[j]- 1/3|+|x[n]-2/5|$.
By computing $(d_1 * 15) \mod 5$, we can know whether $x[n]$ is 0 or 1.
For $i>1$, we have $d_i - d_{i-1} = (\sum_{j=1}^{n-i} |x[j]-a|+\sum_{j=n-i+1}^{n}|x[j]-b|) - (\sum_{j=1}^{n-i+1} |x[j]-a|+\sum_{j=n-i}^{n}|x[j]-b|) = |x[n-i+1]-b|-|x[n-i+1]-a|$. By computing $((d_i-d_{i-1}) * 15) \mod 5$, we can know whether $x[n-i+1]$ is 0 or 1.
Then we can recover all $x[j]$'s using this procedure.

Exact Recovery Algorithm via Queries to DTW Distance Oracle ($\mc{O}(1)$ Extra Chars)

Non-adaptive query sequences $\revise{\mc{Q}} = \{ q^{(1)}, q^{(2)}, \dots, q^{(n+2)} \}$, where $q^{(n+1)} = 0$, $q^{(n+2)} = 1$ and the rest of the queries follows our construction; The DTW distance query results $\revise{\mc{R}} = \{ d_1, d_2, \dots, d_{n+2} \}$ aligned from each query sequence in $\mc{Q}$ to the input sequence to be recovered.
The sequence $s$ to be recovered.
$\revise{\mc{Q}}, \revise{\mc{R}}$
$d_{n+1}$ = 0
s $\coloneqq$ $0^{d_{n+2}}$

$d_{n+2}$ = 0
s $\coloneqq$ $1^{d_{n+1}}$

positions$\coloneqq$ []

coef_1 $\coloneqq$ 0

(Corresponding queries $q^{(i)} = a^{n-i}b^i$)$i \in [1, n]$
$ \text{coef} \coloneqq d_i * 15 * 2 \mod 5$

$(\text{\em coef} - \text{\em coef}\_1 + 5) \mod 5  = 2$

$(\text{\em coef} - \text{\em coef}\_1 + 5) \mod 5 = 3$

coef_1 $\coloneqq$ coef

sequence $\coloneqq$ [], $i \coloneqq 0$

$n\_0$ $\coloneqq$ $d_{n+2}$, $n\_1$ $\coloneqq$ $d_{n+1}$