3 papers
cs.DS2026
Frontier Space-Time Algorithms Using Only Full Memory
Petr Chmel, Aditi Dudeja, Michal Koucký +2
We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only workspace, and use sublinear catalytic spa…
cs.DM2025
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.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…