Sudatta Bhattacharya

activity

20232025

collaborators

4 papers

cs.DM2025

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +4

A function $φ : {0, 1}^{n} \to {0, 1}^{N}$ is called an isometric embedding of the $n$ -dimensional Hamming metric space to the $N$ -dimensional edit metric space if, for all $x,y\in\{0,…

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…

cs.DS2023

Streaming $k$ -edit approximate pattern matching via string decomposition

Sudatta Bhattacharya, Michal Koucký

In this paper we give an algorithm for streaming $k$ -edit approximate pattern matching which uses space $O (k^{2})$ and time $O (k^{2})$ per arriving symbol. This…