Fine-Grained Hardness for Edit Distance to a Fixed Sequence.
Amir AbboudVirginia Vassilevska WilliamsPublished in: ICALP (2021)
Keyphrases
- fine grained
- edit distance
- edit operations
- coarse grained
- longest common subsequence
- levenshtein distance
- string edit distance
- string similarity
- approximate matching
- approximate string matching
- similarity measure
- graph matching
- string matching
- finite alphabet
- distance function
- access control
- minimum cost
- distance measure
- graph edit distance
- tree edit distance
- dynamic programming
- minimal cost
- databases
- tree structured data
- pairwise
- computer vision