Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric

1. Problem Statement

The paper addresses the fundamental problem of embedding the Hamming metric (substitution-only distance) into the Edit metric (Levenshtein distance, allowing insertions, deletions, and substitutions) while preserving distances exactly (isometrically).

• Definitions:
  • Let $\phi: \{0, 1\}^n \to \{0, 1\}^N$ be an embedding.
  • Isometric: $\Delta_{\text{edit}}(\phi(x), \phi(y)) = \Delta_{\text{Hamming}}(x, y)$ for all $x, y$.
  • Rate: Defined as $n/N$.
• The Gap: Prior to this work, the best known isometric embeddings had a rate of $O(1/\log n)$. Achieving a positive constant rate (where $n/N = \Omega(1)$) was an open problem.
• Goal: Determine if constant-rate isometric embeddings exist, find the optimal rate, and understand the structural constraints of such embeddings.

2. Methodology and Technical Framework

The authors develop a novel framework combining synchronization strings and a new object called misaligners.

A. Synchronization Strings and Locally Self-Matching Strings

The authors utilize $\epsilon$-locally self-matching strings (closely related to synchronization strings introduced by Haeupler and Shahrasbi).

• Definition: A string $w$ is $\epsilon$-locally self-matching if for every substring $s$, the nowhere-vertical Longest Common Subsequence ($\tilde{\text{LCS}}$) satisfies $\tilde{\text{LCS}}(s, s) < \epsilon |s|$.
• Contribution: They improve the analysis of constructing these strings, reducing the hidden constants in the alphabet size bound. They prove that for $\epsilon \in (0, 1/2]$, such strings exist over an alphabet of size $|\Sigma| \geq \frac{e^2}{\epsilon^2}(1 + 4\sqrt[4]{\epsilon})$.

B. Misaligners

The core technical innovation is the misaligner, a code in the edit metric with robust distance guarantees.

• Structure: A set of codewords over $\{0, 1, \star\}$ (where $\star$ is a wildcard) of length $m$. Every $t$-th symbol is a wildcard.
• Properties:
  1. Short Intervals: Any substring of length $\leq 3m-2$ formed by concatenating codewords maintains isometry regardless of wildcard instantiation.
  2. Block vs. Substring: The edit distance between a full codeword and any substring of a concatenation of other codewords is large (relative distance $\alpha$).
  3. Robustness: Even if a codeword is compared against a "shifted" version of itself (concatenation of suffix/prefix of other codewords), the distance remains large.
• Construction: The authors used computer search to find a $(320, 676, 8, 0.1625)$-misaligner.

C. The Embedding Construction

The embedding $\phi$ works as follows:

1. Generate a long $\epsilon$-locally self-matching string $w$ over a large alphabet $\Sigma$.
2. Map each symbol of $w$ to a codeword from the misaligner set.
3. Replace the wildcard symbols ($\star$) in the resulting string with the bits of the input string $x$.
4. The output is a binary string where the input bits are "interleaved" with fixed patterns derived from the misaligner and the self-matching string.

3. Key Contributions and Results

A. Existence of Constant Rate Isometric Embeddings

• Theorem 1.1: There exists a universal constant $C$ such that for every $n$, there is an isometric embedding $\{0, 1\}^n \to \{0, 1\}^{Cn}$.
• Theorem 1.7 (Explicit Construction): The authors construct an explicit isometric embedding with a rate of $1/8$.
  • This is achieved by combining the $(320, 676, 8, 0.1625)$-misaligner with a $0.224$-locally self-matching string.
  • Speculation: With larger computational resources (larger $m$, smaller $\epsilon$), the rate could potentially approach $1/5$.

B. Structural Characterization (Interleaving)

• Theorem 1.11: Every isometric embedding of the Hamming metric into the Edit metric must be an interleaved embedding.
  • This means the output string is formed by permuting input bits, potentially flipping them, and interleaving them with fixed "frozen" strings.
  • This structural constraint is crucial for proving upper bounds.

C. Upper Bounds on Rate

• Theorem 1.12: For binary strings, no isometric embedding can have a rate greater than $15/32$ (approx 0.468).
  • Note: The paper mentions a subsequent improvement by Bhattacharya to $3/7 + o(1)$.
• Theorem 1.13: For an alphabet $\Sigma$, the rate is bounded by $\frac{1}{2} - \frac{1}{16|\Sigma|}$.
  • This proves that for any fixed alphabet, the rate is strictly bounded away from $1/2$.

D. Breaking the Barrier with Different Alphabets

• Theorem 1.15: If the input and output alphabets are allowed to differ ($\Sigma_{in} \neq \Sigma_{out}$), the rate (defined as $\frac{n \log |\Sigma_{in}|}{N \log |\Sigma_{out}|}$) can be made arbitrarily close to 1.
  • This is achieved by using a large output alphabet to encode the "synchronization" overhead efficiently in terms of bits.

E. Improved Lower Bounds for Computational Problems

The constant-rate embedding allows transferring hardness results from Hamming space to Edit space with optimal dimension dependency. Previously, reductions resulted in dimensions of $O(\log n \cdot \log \log n)$; now they are $O(\log n)$.

• Closest Pair & 1-Center: Conditional lower bounds of $\Omega(N^{2-\delta})$ under SETH and Hitting Set Conjecture.
• Clustering & Steiner Tree: Improved NP-hardness of approximation factors.
• Communication Complexity:
  • Gap-Edit Problem: Proves an $\Omega(n)$ randomized communication complexity lower bound.
  • Exact-Edit Problem: Proves a lower bound of $(1/8 - o(1))n$ bits (improving over the trivial $\Omega(n)$).

4. Significance and Impact

1. Resolution of a Long-Standing Open Problem: The paper definitively answers that constant-rate isometric embeddings exist, moving the field from logarithmic rates to constant rates.
2. New Structural Insight: The proof that all isometric embeddings must be interleaved provides a powerful tool for analyzing the limits of such mappings and proving impossibility results.
3. Hardness Transfers: By enabling embeddings with optimal dimension dependency, the paper strengthens the theoretical foundations for the hardness of edit distance problems, linking them more tightly to the complexity of Hamming distance problems.
4. Algorithmic Tools: The introduction of misaligners and the refined analysis of synchronization strings provide new tools for coding theory, specifically for insertion-deletion codes and error correction.
5. Communication Complexity: The results settle the complexity of the Gap-Edit problem and provide new lower bounds for the Exact-Edit problem, which were previously unknown or weak.

In summary, this work fundamentally changes the understanding of the relationship between Hamming and Edit metrics, providing constructive methods for high-rate embeddings while simultaneously establishing tight theoretical limits on their performance.