3 papers
cs.DM2026
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +4
A function is called an isometric embedding of the -dimensional Hamming metric space to the -dimensional edit metric space if, for all $x,y\in\{0…
cs.DS2025
Hardness of Median and Center in the Ulam Metric
Nick Fischer, Elazar Goldenberg, Mursalin Habib +1
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamenta…
cs.DS2024
Many Flavors of Edit Distance
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +1
Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and subs…