Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric

In computational complexity, it is typically easier to prove the intractability of problems in the Hamming metric, and in such a situation, if we had a 1-embedding of the Hamming metric into the edit metric, then the hardness result would translate to the edit metric as well. These embeddings have been studied in the literature for exactly this purpose. For instance, a folklore embedding¹¹1See, for example, Lemma 11 in [2]. from the Hamming metric to the edit metric constructs the output string by inserting a uniformly random block of size $\mathrm{\Theta }(\log n)$ after each character of the input string. This can be shown to result in an isometric embedding with high probability (and can be derandomized using constant relative distance codes in the edit metric, such as the ones in [36]).

However, this embedding achieves a rate of only $\frac{1}{\mathrm{\Theta }(\log n)}$. Consequently, this implies that if a problem is hard for strings of length $n$ in the Hamming metric, then it remains hard in the edit metric, but only for strings of length $\mathrm{\Theta }(n\log n)$. On the other hand, our intuition suggests that solving problems in the $n$-dimensional edit metric should be at least as hard as solving the same problems in the $n$-dimensional Hamming metric. The inability to provide a formal justification for this intuition leaves us wanting for a clearer understanding. To address this gap, we aim to answer the following natural question:

Does there exist a 1-embedding of the Hamming metric into the edit metric
with positive constant rate?

Our first result is an affirmative answer to the above question (in fact, we provide an isometric embedding). Our conceptual contribution in this regard is a clean connection between synchronization strings studied in the context of the study of codes for correcting insertion and deletion errors [19, 21, 17, 20, 10] with the above question.

This represents a sharp improvement: even for the weaker notion of near-isometric embeddings, the previously best known rate was only $\frac{1}{\mathrm{\Theta }(\log n)}$ [35].

We remark here that although the proof of Theorem 1 is, in hindsight, simple and natural (see Section 2.1 for a proof sketch), the route to it was not obvious. Synchronization strings have been designed in literature to trade alphabet size for approximation accuracy, and had been regarded primarily as an approximation tool. It was not evident, at least to us, that they could be leveraged to obtain isometric embeddings.

As an immediate consequence of Theorem 1, we obtain the following meta theorem for discrete optimization problems in the edit metric. By discrete, we mean that the input is a set of points in the metric space, and the solution is some subset of the input points. For such problems, we have the following.

If a discrete optimization problem defined in the $n$-dimensional Hamming metric
cannot be solved in time $T(n)$ (for some computable function $T$),
then the same optimization problem defined in the $n$-dimensional Edit metric
cannot be solved in time $T(\mathrm{\Theta }(n))$.

As concrete manifestations of this meta theorem, we prove optimal hardness results in two distinct settings. We remark that in the case of all the three theorems below, i.e., Theorems 2, 3, and 6, the previously known lower bounds or hardness results in the edit metric over binary strings was only for dimensions $d=O(\log n\cdot \log \log n)$, where the earlier mentioned embedding with rate $\mathrm{\Theta }\left(\frac{1}{\log d}\right)$ was used. Thus, by reducing the dimension to $d=O(\log n)$ in the three theorems below, we obtain optimal dependency in the dimension.

While Theorem 1 provides a constant-rate isometric embedding of the Hamming metric into the edit metric, the guaranteed rate is quite small. In certain natural applications, however, it is important that we have high-rate embeddings. Below, we present three concrete motivations for finding isometric embeddings that maximize the rate.

The embedding in Theorem 8 is an example of an interleaved embedding, where the output string is formed by interleaving the input bits with sequences of bit strings that do not depend on the input. A natural question is whether there exist isometric embeddings, potentially with better rates, that do not follow this interleaving framework. We answer this negatively, demonstrating that isometry necessitates an interleaved structure in the output strings.

A precise formulation of Theorem 11 requires a formal definition of interleaved embeddings, which we provide in Section 10 of the full version of the paper [6]. Informally, we naturally extend the intuitive notion of interleaving input bits with fixed bit patterns by allowing two additional flexibilities. First, we allow the input bits to appear out-of-order – e.g., the second input bit might appear after the first input bit in the output string. We further allow some of the input bits to appear complemented in the output string. Thus, an isometric embedding of the Hamming metric into the edit metric is completely determined by three components – the order in which input bits appear in the output, the subset of input bits that are flipped, and the sequence of fixed bit strings that are to be interleaved with the input bits.

This structural constraint on Hamming-to-edit isometric embeddings enables us to derive bounds on the achievable rate. In particular, we show that for binary strings, any isometric embedding must stretch the input strings by a factor greater than 2.133.

We note that the above upper bound on rate has been improved by Bhattacharya (see Theorem 4.30 in [5]) to $\frac{3}{7}+o(1)$.

Next, we generalize Theorem 12 to larger alphabets by first extending the definition of interleaved embeddings to larger alphabets (See Section 10.1 of the full version of the paper [6]), then proving that every isometric embedding must be an interleaved embedding, and finally showing an analogous statement to Theorem 12.

Having established the rate limitations for isometric embeddings over the binary alphabet, we next explore if leveraging a larger alphabet $\mathrm{\Sigma }$ enables the construction of embeddings $\phi :{\mathrm{\Sigma }}^n\to {\mathrm{\Sigma }}^N$ with potentially improved rates. As in the binary case, we can obtain high-rate embeddings over $\mathrm{\Sigma }$ by using misaligners for larger alphabets. In fact, it is not hard to see that misaligners designed for the binary alphabet also function as misaligners for larger alphabets, without any loss in parameters. Therefore, increasing the alphabet size can only improve the achievable rate.

We show that even without relying on the full machinery of misaligners, one can obtain isometric embeddings with rates arbitrarily close to $\frac{1}{3}$ by making the alphabet large enough.

Theorem 13 tells us that as long as the input and output alphabets remain the same, the rate in Theorem 14 can never be improved to $\frac{1}{2}$ or anything better. But what if we allow the input and output alphabets to be different?

In this setting, our notion of rate needs to be refined. In particular, when using the larger output alphabet, the appropriate measure to consider is not the lengths of strings but the number of bits contained in them. Thus, for an embedding $\phi :{\mathrm{\Sigma }}_{\text{in}}\to {\mathrm{\Sigma }}_{\text{out}}$, we define the rate as $\frac{n\log |{\mathrm{\Sigma }}_{\text{in}}|}{N\log |{\mathrm{\Sigma }}_{\text{out}}|}$. With this refined definition, we show that not only can the $\frac{1}{2}$ rate barrier be surpassed, but the rate can actually be made arbitrarily close to 1!

We provide a proof of Theorem 15 in Section 12 of the full version of the paper [6]. Theorem 14 is proven in Section 9 of the same full version [6].

In this subsection, we survey three lines of related works.

Due to the page limit for the conference proceedings, this version focuses on the proof overview and defers all formal proofs to the full version of the paper [6]. In Section 2, we provide an overview of the proofs for our main results. The full version contains the formal proof of Theorem 7 in Section 8, Theorem 14 in Section 9, Theorem 11 in Section 10, Theorem 13 in Section 11, and Theorem 15 in Section 12 [6]. In addition, misaligners and locally-self-similar strings – the two key ingredients for our high-rate embedding, are formally introduced and analyzed in Sections 4 and 5 of the same full version [6].

Our first observation is that if we are allowed an unbounded output alphabet, then there is a straightforward isometric embedding that takes any input string and interleaves it with a string with all distinct symbols. This embedding is clearly isometric since any misalignment of these new symbols results in mismatches, increasing the edit cost beyond that of the simple identity alignment, which equals the Hamming distance between the input strings. Moreover, the length of the output strings produced by this embedding is only twice that of the input strings.

However, our goal is to have a binary output alphabet, not an unbounded one. So, as an intermediate step, let us limit ourselves to a large but constant-sized output alphabet. Now, if we want to mimic our earlier embedding, we would need to find a string over a constant-sized alphabet that approximates the string with all distinct symbols. It turns out that objects known as synchronization strings [19] have the exact property that we want. Synchronization strings have many equivalent definitions. The one that is useful for our discussion is the following – a string is said to be an $\epsilon$-synchronization string if, for every substring, its relative self-edit distance⁴⁴4The self-edit distance of a string is the cost of the cheapest alignment converting the string to itself without matching any character to itself. is at least $1-\epsilon$. For every value of $\epsilon$, one can efficiently construct $\epsilon$-synchronization strings over an alphabet of size $\mathrm{\Theta }(1/{\epsilon }^2)$ [10]. We now illustrate how these strings can be used to construct constant-rate isometric embeddings over a large but fixed-size output alphabet.

To embed a string of length $n$, consider a $2/3$-synchronization string of length $3n$ over an alphabet $\mathrm{\Sigma }$ that is disjoint from the input alphabet $\{0,1\}$. The embedding process, applied to an input string of length $n$, involves inserting $3$ symbols from the synchronization string after every input symbol. It is evident that both the rate and the output alphabet size remain constant.

We now argue that this gives an isometric embedding. Suppose it does not; then there must be a pair of strings such that the edit distance between their embeddings is strictly smaller than their Hamming distance. Consider an optimal edit alignment of the embedded strings. It can be shown that this alignment partitions the strings into intervals, where for each interval in the partition, either the entire interval is mapped using the identity mapping, i.e., “vertical”, or it is self-aligned such that none of its characters are mapped to themselves, i.e., “nowhere-vertical”. See Figure 1 for an illustration.

Now, if the edit distance is indeed strictly less than the Hamming distance, then there is at least one interval, say of length $\mathrm{\ell }$, in this partition where none of its characters are mapped to themselves, but the edit cost in that interval is strictly less than the Hamming cost, which is at most $\mathrm{\ell }/4$. We then show that this implies the existence of a substring in the synchronization string with a relative self-edit distance less than $1/3$, which is a contradiction. This substring can be found by considering the aforementioned interval and deleting all the characters that come from the input strings. This results in a substring with length ${\mathrm{\ell }}^{\prime }:=3\mathrm{\ell }/4$. One can also find a self-alignment of this substring by taking the original alignment, keeping it unchanged except for positions where some character in the substring was matched to some character in one of the input strings. In those positions, we simply apply a deletion. It is not hard to see that the cost of this alignment remains unchanged and is thus less than $\mathrm{\ell }/4={\mathrm{\ell }}^{\prime }/3$, which contradicts the fact that the string used to pad is a $2/3$-synchronization string. In Figure 2, the red characters are part of some $\epsilon$-synchronization string, and the green ones are part of some input string.

One can then bring the output alphabet size down to two using the following alphabet reduction procedure – we replace each character of the synchronization string with its binary encoding (of length $\log |\mathrm{\Sigma }|$) along with an opening and closing block of $0$s and $1$s with lengths equal to that of the binary encoding. The final resulting rate is still constant. However, the large alphabet sizes required to construct $\epsilon$-synchronization strings mean that the resulting rate is far from optimal. With the specific setting of $\epsilon =2/3$ and known bounds for alphabet sizes for synchronization strings, one gets a rate of about $1/153$ from this.

To improve the rate of our embedding, we move away from the framework of interleaving a synchronization string over a larger alphabet and then performing an alphabet reduction. Instead, we utilize a tailored construction that gives us a much larger rate.

The key ingredient in our construction is an object called a misaligner, which the reader should think of as a code in the edit metric with robust distance guarantees. A misaligner consists of a set of fixed-length codewords over the alphabet $\{0,1,\star \}$, where $\star$ is a special wildcard symbol. Each codeword contains a wildcard symbol at every $t^{\text{th}}$ position, where $t$ is a parameter that controls the rate of the embedding. Thus, if one concatenates a sequence of codewords from the misaligner, one obtains a long binary string with wildcard symbols at every $t^{\text{th}}$ position. To embed some input string, one simply substitutes these wildcard symbols with symbols from the input string. The rate of this embedding is $1/t$ by definition.

To fully describe the embedding, one also needs to specify the order in which codewords from the misaligner are concatenated. To do this, we make use of a variant of synchronization strings, which we call locally self-matching strings. Given $\epsilon \in (0,1)$, an $\epsilon$-locally self-matching string is one where every substring of length $\mathrm{\ell }$ has at most $\epsilon \mathrm{\ell }$ non-crossing symbol matches to itself if one is not allowed to match symbols vertically.⁵⁵5Alternatively, every substring has “nowhere-vertical” relative LCS at most $\epsilon$; see Section 5 in the full version [6] for a formal definition. Given both these ingredients, we can now describe our embedding. To embed an input string, we first start with a sufficiently long locally self-matching string over some large alphabet. Next, we replace each symbol of this string with a codeword from the misaligner. Note that in order to do this, the number of codewords in the misaligner must be at least as large as the alphabet of the locally self-matching string. Finally, we substitute the wildcard symbols in this string with symbols of the input string to obtain the embedded string. Our goal is to show that by choosing $t$ sufficiently large, the properties of the locally self-matching string and the misaligner guarantee that the resulting construction is an isometric embedding.

For concreteness, in the remainder of this section, let us assume that a 0.1-locally self-matching string $s$ exists over some large alphabet $\mathrm{\Sigma }$. We also assume that a misaligner $𝒞$ with $|\mathrm{\Sigma }|$ many codewords exists. The other properties of this misaligner will be specified later. We will show how the properties of $s$ and $𝒞$ will guarantee isometry.

Let us call a codeword with its wildcard symbols instantiated a block. Assume for the sake of contradiction that the embedding we just described is not an isometric embedding. As before, this implies the existence of an interval with an edit cost that is strictly lower than its Hamming cost. The first guarantee that the misaligner provides is that this interval must contain at least two full blocks. This is ensured by enforcing the codewords of the misaligner to have the following property – for any substring arising from the concatenation of multiple codewords and not containing two full blocks must have the edit distance equal to the Hamming distance, no matter how the wildcard symbols are instantiated. See Figure 3 for an illustration of this property.

For larger intervals (i.e., intervals containing at least two full blocks), we assume for simplicity that the interval consists solely of a sequence of full blocks with no partial blocks at the boundaries. The analysis then goes on to assess the cost of the optimal alignment by decomposing it into contributions from individual blocks. Our objective is to demonstrate that, for most blocks, there is a substantial cost, which, for the purposes of this discussion, is 0.2 times the length of a block.

Our first observation concerns any pair of blocks within the specified interval that are instantiations of the same codeword but appear at different positions in the embedded strings. It can be shown (Obervation 7.1 in the full version [6]) that we can assume that in our optimal alignment, exactly one of the following cases occurs: either all of the characters of one of the blocks are matched “vertically” to all of the characters in the other block⁶⁶6By “vertically”, we mean the $i^{\text{th}}$ character of the first block is matched against the $i^{\text{th}}$ character of the second. (in which case, the first block is referred to as “bad”; see Figure 4), or none of the characters are matched “vertically”. From the set of bad blocks and their matches, one can recover a sequence of nowhere-vertical matches in the original locally self-matching string $s$. Since $s$ was a 0.1-locally self-matching string, one can thus conclude that the fraction of bad blocks is at most 0.1.

Next, let us analyze the remaining blocks. The optimal alignment transforms each of these blocks into a substring coming from the concatenation of multiple blocks. If the size of this substring exceeds $0.2$ times the block size, then the cost will also exceed $0.2$. For the remaining blocks, the misaligner must ensure that the edit cost of each block remains substantial. This can be accomplished by satisfying the following requirements:

Consider a block $b$ and take any substring $s$ of roughly the same size, composed of partial blocks. If none of these blocks is equal to $b$, we require that the relative edit cost between $b$ and $s$ is at least $0.2$. If one of these blocks is equal to $b$, we require that the edit cost of alignments with no vertical edges between $b$ and its counterpart in $s$ is at least $0.2$. See Figure 5 for an illustration.

Since bad blocks cost zero, the total cost is given by the sum of costs incurred by the non-bad blocks. Thus, by the properties of the misaligner and the locally self-matching string, the relative cost is lower bounded by $(1-0.1)\times 0.2=0.18$. Therefore, if we choose $t=6$, we arrive at a contradiction, as the cost would then exceed the number of wildcards, which is an upper bound on the Hamming distance in the interval between any two strings. Consequently, we can achieve a $1/6$-rate isometric embedding. The case where the interval may contain partial blocks introduces additional requirements, which are detailed in Section 4 of the full version of the paper [6].

In this section, we outline the key ideas behind our proof of Theorem 11, which states that every isometric embedding of the Hamming metric into the edit metric is necessarily an interleaved embedding. The formal definition of interleaved embeddings is given in Section 10 of the full version of the paper [6]. Here, we instead fix an arbitrary isometric embedding $\phi :{\{0,1\}}^n\to {\{0,1\}}^N$ and make a series of observations that reveal certain constraints on $\phi$, ultimately uncovering its interleaved nature.

We start by fixing an input string $x\in {\{0,1\}}^n$ and ask what happens to $\phi (x)$ as we flip a single bit in $x$. Since $\phi$ is isometric, flipping a single bit in $x$ must correspond to exactly one bit flip in $\phi (x)$. This allows us to define a function ${\eta }_x:[n]\to [N]$, ${\eta }_x(i)$ is the unique index in $\phi (x)$ that is flipped if the $i^{\text{th}}$ bit of $x$ is flipped.

Next, we show that the function ${\eta }_x$ is injective, meaning that different bit flips in $x$ affect different positions in the output $\phi (x)$. This is not hard to see – if two different bit-flips in $x$ affected the same position in $\phi (x)$, then we would obtain a pair of strings at Hamming distance 2 whose images under $\phi$ have edit distance 0, contradicting the fact that $\phi$ is isometric.

A crucial step in the proof is showing that ${\eta }_x(i)$ does not depend on $x$. That is, once $i$ is fixed, flipping the $i^{\text{th}}$ bit in any input string always affects the same location in the output. This means the function ${\eta }_x$ is the same for all inputs and can simply be written as $\eta$. This can be proven by fixing a pair of input strings $x,y$ and an index $i$ and inducting on the Hamming distance between $x$ and $y$. This key step is presented in detail in Section 10 of the full version [6].

Finally, we show that $\phi (x)[\eta (i)]$ depends only on $x[i]$, meaning that each input bit is mapped consistently to the same output position, either preserving or flipping its value. With this, the interleaved nature of $\phi$ is revealed: the output positions fall into two categories – those that directly correspond to input bits (determined by $\eta$) and the remaining positions that are independent of the input.

In this section, we outline the proof of Theorem 13, which establishes that any isometric embedding of the Hamming metric into the edit metric must have a rate strictly bounded away from $\frac{1}{2}$. More precisely, we aim to show that for any alphabet $\mathrm{\Sigma }$, there exists some $\epsilon >0$ such that for sufficiently large $n$, no isometric embedding $\phi :{\mathrm{\Sigma }}^n\to {\mathrm{\Sigma }}^N$ can achieve a rate exceeding $\frac{1}{2}-\epsilon$.

Our approach is by contradiction: we assume that for all $n$, there exists an isometric embedding $\phi$ with a rate exceeding the claimed bound. The goal then is to show that as $n$ grows, $\phi$ cannot remain isometric. Specifically, we seek a pair of strings such that the edit distance between their embeddings is strictly smaller than their Hamming distance, contradicting isometry. Rather than constructing such a pair explicitly, we will argue its existence via the probabilistic method.

The key idea is to consider a collection $𝒞$ of carefully chosen triples $(x,y,𝒜)$, where $x,y\in {\mathrm{\Sigma }}^n$ and $𝒜$ is an edit distance alignment between $\phi (x)$ and $\phi (y)$. We then select a random triple from $𝒞$ and show that the expected cost of $𝒜$ with respect to the embeddings $\phi (x)$ and $\phi (y)$ is too low, ensuring the existence of a triple in $𝒞$ that violates the isometry of $\phi$.