research
∙
02/14/2023
Compressibility-Aware Quantum Algorithms on Strings
Sublinear time quantum algorithms have been established for many fundame...
share
research
∙
01/28/2022
The Complexity of Approximate Pattern Matching on De Bruijn Graphs
Aligning a sequence to a walk in a labeled graph is a problem of fundame...
research
∙
08/26/2020
Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism
The CNF formula satisfiability problem (CNF-SAT) has been reduced to man...
research
∙
11/08/2019
On the Complexity of BWT-runs Minimization via Alphabet Reordering
We present the first set of results on the computational complexity of m...
research
∙
02/05/2019
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
In recent years several compressed indexes based on variants of the Borr...
research
∙
05/16/2018