research
∙
11/14/2022
Bellman-Ford is optimal for shortest hop-bounded paths
This paper is about the problem of finding a shortest s-t path using at ...
share
research
∙
04/06/2022
Faster Pattern Matching under Edit Distance
We consider the approximate pattern matching problem under the edit dist...
research
∙
11/24/2021
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
We study the problem of approximating edit distance in sublinear time. T...
research
∙
06/24/2021
Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays
The suffix array, describing the lexicographic order of suffixes of a gi...
research
∙
10/23/2019
Resolution of the Burrows-Wheeler Transform Conjecture
Burrows-Wheeler Transform (BWT) is an invertible text transformation tha...
research
∙
10/04/2019
Towards a Definitive Measure of Repetitiveness
Unlike in statistical compression, where Shannon's entropy is a definiti...
research
∙
07/03/2019
Circular Pattern Matching with k Mismatches
The k-mismatch problem consists in computing the Hamming distance betwee...
research
∙
02/28/2019
