research
∙
07/31/2023
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Algorithms with predictions incorporate machine learning predictions int...
share
research
∙
07/14/2023
Approximating Edit Distance in the Fully Dynamic Model
The edit distance is a fundamental measure of sequence similarity, defin...
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...
research
∙
11/22/2022
An Algorithmic Bridge Between Hamming and Levenshtein Distances
The edit distance between strings classically assigns unit cost to every...
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
∙
06/22/2022
Community Recovery in the Geometric Block Model
To capture inherent geometric features of many community detection probl...
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
∙
12/10/2021
How Compression and Approximation Affect Efficiency in String Distance Measures
Real-world data often comes in compressed form. Analyzing compressed dat...
research
∙
11/24/2021
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
We study the problem of approximating edit distance in sublinear time. T...
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
∙
08/20/2021
Does Preprocessing help in Fast Sequence Comparisons?
We study edit distance computation with preprocessing: the preprocessing...
research
∙
05/12/2021
How to Design Robust Algorithms using Noisy Comparison Oracle
Metric based comparison operations such as finding maximum, nearest and ...
research
∙
07/24/2020
Sublinear-Time Algorithms for Computing Embedding Gap Edit Distance
In this paper, we design new sublinear-time algorithms for solving the g...
research
∙
05/28/2020
Efficient and Effective ER with Progressive Blocking
Blocking is a mechanism to improve the efficiency of Entity Resolution (...
research
∙
10/02/2019
Sublinear Algorithms for Gap Edit Distance
The edit distance is a way of quantifying how similar two strings are to...
research
∙
08/14/2019
Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost
Several clustering frameworks with interactive (semi-supervised) queries...
research
∙
06/28/2019
Min-Max Correlation Clustering via MultiCut
Correlation clustering is a fundamental combinatorial optimization probl...
research
∙
05/28/2019
Paper Matching with Local Fairness Constraints
Automatically matching reviewers to papers is a crucial step of the peer...
research
∙
04/12/2018
Connectivity in Random Annulus Graphs and the Geometric Block Model
Random geometric graphs are the simplest, and perhaps the earliest possi...
research
∙
04/09/2018
Fully Dynamic Set Cover -- Improved and Simple
In this paper, we revisit the unweighted set cover problem in the fully ...
research
∙
09/16/2017
The Geometric Block Model
To capture the inherent geometric features of many community detection p...
research
∙
06/23/2017
Query Complexity of Clustering with Side Information
Suppose, we are given a set of n elements to be clustered into k (unknow...
research
∙
06/22/2017
Clustering with Noisy Queries
In this paper, we initiate a rigorous theoretical study of clustering wi...
research
∙
02/03/2017