Mursalin Habib, Rutgers University

Abstract

A function that maps n-bit strings to N-bit strings is called an isometric embedding of the n-dimensional Hamming metric space to the N-dimensional edit metric space if the Hamming distance between any pair of input strings equals the edit distance between the corresponding output strings. The rate of such an embedding is defined as the ratio n/N.

It is well known in the literature how to construct isometric embeddings with a rate of 1/logn. However, achieving even near-isometric embeddings with a positive constant rate has remained elusive until now.

In this talk, I will talk about our recent work giving the first ever constant rate isometric embedding of the Hamming metric into the edit metric. In particular, I will describe an isometric embedding with a rate of 1/8 by discovering connections to synchronization strings, which were studied in the context of insertion-deletion codes (Haeupler-Shahrasbi [JACM'21]).

As an immediate consequence of our constant rate isometric embedding, we improve known conditional lower bounds for the closest pair problem and the discrete 1-center problem in edit metric and NP-hardness of approximation results for clustering problems and the Steiner tree problem in the edit metric, but now with optimal dependency on the dimension.

At a technical level, we introduce a framework for obtaining high-rate isometric embeddings using novel objects called misaligners. We speculate that, with sufficient computational resources, our framework could potentially yield isometric embeddings with a rate of 1/5. We also give upper bounds on the rate of any isometric embedding.

This is joint work with: Sudatta Bhattacharya, Elazar Goldenberg, Sanjana Dey, Bernhard Haeupler, Karthik C.S., and Michal Koucký.

See: https://theory.cs.rutgers.edu/theory_seminar