research
∙
02/13/2023
Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
We give an Õ(n^2) time algorithm for computing the exact Dynamic Time Wa...
share
research
∙
11/03/2021
An Improved Algorithm for The k-Dyck Edit Distance Problem
A Dyck sequence is a sequence of opening and closing parentheses (of var...
research
∙
06/24/2020
Improved Circular k-Mismatch Sketches
The shift distance 𝗌𝗁(S_1,S_2) between two strings S_1 and S_2 of the sa...
research
∙
04/27/2020
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
We revisit the k-mismatch problem in the streaming model on a pattern of...
research
∙
03/04/2020
Time-Space Tradeoffs for Finding a Long Common Substring
We consider the problem of finding, given two documents of total length ...
research
∙
01/01/2020
Approximating Text-to-Pattern Hamming Distances
We revisit a fundamental problem in string matching: given a pattern of ...
research
∙
12/02/2018