3 papers
cs.DS2022
-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…
cs.DS2021
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…
cs.CC2018
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…