research
∙
02/08/2023
Weighted Edit Distance Computation: Strings, Trees and Dyck
Given two strings of length n over alphabet Σ, and an upper bound k on t...
share
research
∙
12/04/2022
Clustering Permutations: New Techniques with Streaming Applications
We study the classical metric k-median clustering problem over a set of ...
research
∙
09/15/2022
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance
Computing the edit distance of two strings is one of the most basic prob...
research
∙
12/10/2021
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
The Dyck language, which consists of well-balanced sequences of parenthe...
research
∙
11/14/2021
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Given an n-vertex planar embedded digraph G with non-negative edge weigh...
research
∙
10/24/2021
Approximating LCS and Alignment Distance over Multiple Sequences
We study the problem of aligning multiple sequences with the goal of fin...
research
∙
10/06/2021
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
We consider the numerical taxonomy problem of fitting a positive distanc...
research
∙
07/20/2021
Approximate Trace Reconstruction via Median String (in Average-Case)
We consider an approximate version of the trace reconstruction problem, ...
research
∙
06/15/2021
A Linear-Time n^0.4-Approximation for Longest Common Subsequence
We consider the classic problem of computing the Longest Common Subseque...
research
∙
11/02/2020
Approximating the Median under the Ulam Metric
We study approximation algorithms for variants of the median string prob...
research
∙
04/02/2020
No Repetition: Fast Streaming with Highly Concentrated Hashing
To get estimators that work within a certain error bound with high proba...
research
∙
10/08/2018
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Edit distance is a measure of similarity of two strings based on the min...
research
∙
10/08/2018
Approximate Online Pattern Matching in Sub-linear Time
We consider the approximate pattern matching problem under edit distance...
research
∙
01/16/2018
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
In this paper we propose models of combinatorial algorithms for the Bool...
research
∙
12/05/2017