Elazar Goldenberg, Academic College of Tel Aviv-Yaffo

Abstract

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings lying in the Boolean hypercube. The edit distance between a pair of strings is defined as the minimum number of character insertion, deletion, and bit flips needed for converting one string into another. In contrast, the Hamming distance between strings is simply the number of bit flips needed to convert them. In this talk I will present a randomized injective embedding of the edit distance into the Hamming distance with a small (quadratic) distortion. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input. If time allows, I will also discuss a possible direction connecting this result and the challenge of proving the hardness of approximation for edit distance. This is based on a joint work with Diptarka Chakraborty and Michal Koucky.

[Video]