1 citations · 1 across the 6 of their papers we have counts for
6 papers
Weighted Edit Distance Computation: Strings, Trees and Dyck
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
Given two strings of length over alphabet , and an upper bound on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…
Clustering Permutations: New Techniques with Streaming Applications
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
We study the classical metric -median clustering problem over a set of input rankings (i.e., permutations), which has myriad applications, from social-choice theory to web searc…
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg +1
Given an -vertex planar embedded digraph with non-negative edge weights and a face of , Klein presented a data structure with space and preprocessing tim…
A Linear-Time -Approximation for Longest Common Subsequence
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length . While a simple quadratic algorithm has been known for the problem fo…
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Debarati Das, Michal Koucký, Michael Saks
In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a r…