research
∙
07/18/2023
Cut Sparsification and Succinct Representation of Submodular Hypergraphs
In cut sparsification, all cuts of a hypergraph H=(V,E,w) are approximat...
share
research
∙
07/15/2023
Fully Scalable MPC Algorithms for Clustering in High Dimension
We design new algorithms for k-clustering in high-dimensional Euclidean ...
research
∙
11/10/2022
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Max-Cut is a fundamental problem that has been studied extensively in va...
research
∙
07/04/2022
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
In vertex-cut sparsification, given a graph G=(V,E) with a terminal set ...
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
∙
11/09/2021
Gomory-Hu Tree in Subcubic Time
In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...
research
∙
11/03/2020
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Many real-world data sets are sparse or almost sparse. One method to mea...
research
∙
11/02/2020
Approximating the Median under the Ulam Metric
We study approximation algorithms for variants of the median string prob...
research
∙
02/18/2020
Faster Algorithms for Orienteering and k-TSP
We consider the rooted orienteering problem in Euclidean space: Given n ...
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
∙
07/10/2019
Coresets for Clustering in Graphs of Bounded Treewidth
We initiate the study of coresets for clustering in graph metrics, i.e.,...
research
∙
11/06/2018
Flow-Cut Gaps and Face Covers in Planar Graphs
The relationship between the sparsest cut and the maximum concurrent mul...
research
∙
07/16/2018
