Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Almost Linear Size Edit Distance Sketch
Michal Koucký, Michael Saks
Edit distance is an important measure of string similarity. It counts the number of insertions, deletions and substitutions one has to make to a string to get a string . In…
cs.DS2024
Nearly Optimal List Labeling
Michael A. Bender, Alex Conway, Martín Farach-Colton +4
The list-labeling problem captures the basic task of storing a dynamically changing set of up to elements in sorted order in an array of size . The goal is to…