research
∙
08/30/2023
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Given a signed permutation on n elements, we need to sort it with the fe...
share
research
∙
04/03/2023
Compressed Indexing for Consecutive Occurrences
The fundamental question considered in algorithms on strings is that of ...
research
∙
08/31/2022
Pattern matching under DTW distance
In this work, we consider the problem of pattern matching under the dyna...
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/10/2021
Small space and streaming pattern matching with k edits
In this work, we revisit the fundamental and well-studied problem of app...
research
∙
04/28/2020
Approximating longest common substring with k mismatches: Theory and practice
In the problem of the longest common substring with k mismatches we are ...
research
∙
01/16/2020
Generalised Pattern Matching Revisited
In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukris...
research
∙
01/05/2020
All non-trivial variants of 3-LDT are equivalent
The popular 3-SUM conjecture states that there is no strongly subquadrat...
research
∙
09/23/2019
Sliding window property testing for regular languages
We study the problem of recognizing regular languages in a variant of th...
research
∙
07/09/2019
L_p Pattern Matching in a Stream
We consider the problem of computing distance between a pattern of lengt...
research
∙
12/21/2018
Lower bounds for text indexing with mismatches and differences
In this paper we study lower bounds for the fundamental problem of text ...
research
∙
09/07/2018
Streaming dictionary matching with mismatches
In the k-mismatch problem we are given a pattern of length m and a text ...
research
∙
06/25/2018
Fast entropy-bounded string dictionary look-up with mismatches
We revisit the fundamental problem of dictionary look-up with mismatches...
research
∙
02/19/2018
Upper and lower bounds for dynamic data structures on strings
We consider a range of simply stated dynamic data structure problems on ...
research
∙
12/22/2017