39 citations · 241 across the 54 of their papers we have counts for
6 papers · 1 filter
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka +1
Classically, the edit distance of two length- strings can be computed in time, whereas an -time procedure would falsify the Orthogonal Vectors Hypothesis. I…
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya
We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most funda…
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
Dominik Kempa, Tomasz Kociumaka
In the last decades, the necessity to process massive amounts of textual data fueled the development of compressed text indexes: data structures efficiently answering queries on a…
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one strin…
Optimal Algorithms for Bounded Weighted Edit Distance
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic…
Weighted Edit Distance Computation: Strings, Trees and Dyck
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
Given two strings of length over alphabet , and an upper bound on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…