Seminars

View all Seminars  |  Download ICal for this event

Constant Rate Isometric Embedding of Hamming Metric into Edit Metric

Series: Bangalore Theory Seminars

Speaker: Karthik C. S., Rutgers University

Date/Time: Feb 21 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
A function phi: {0,1}^n -> {0,1}^N is called an isometric embedding from the n-dimensional Hamming metric space to the N-dimensional edit metric space if, for all x, y in {0,1}^n, the Hamming distance between x and y is equal to the edit distance between phi(x) and phi(y). 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/log n. However, achieving even near-isometric embeddings with a positive constant rate has remained elusive until now.

In this talk, we will present 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]). En route, we also improve the analysis of the construction of synchronization strings that appear in literature.

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 a novel object called misaligners. We speculate that, with sufficient computational resources, our framework could potentially yield isometric embeddings with a rate of 1/5.


Microsoft teams link:

Link

Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar