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
∙
09/11/2020
Quantifying Membership Inference Vulnerability via Generalization Gap and Other Model Metrics
We demonstrate how a target model's generalization gap leads directly to...
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