37 citations · 64 across the 8 of their papers we have counts for
11 papers · 1 filter
-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…
Approximating LCS and Alignment Distance over Multiple Sequences
Debarati Das, Barna Saha
We study the problem of aligning multiple sequences with the goal of finding an alignment that either maximizes the number of aligned symbols (the longest common subsequence (LCS))…
Does Preprocessing help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed…
How to Design Robust Algorithms using Noisy Comparison Oracle
Raghavendra Addanki, Sainyam Galhotra, Barna Saha
Metric based comparison operations such as finding maximum, nearest and farthest neighbor are fundamental to studying various clustering techniques such as -center clustering an…
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
Tomasz Kociumaka, Barna Saha
In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance prob…
Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost
Barna Saha, Sanjay Subramanian
Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algori…