research
∙
03/27/2023
Faster Isomorphism for p-Groups of Class 2 and Exponent p
The group isomorphism problem determines whether two groups, given by th...
share
research
∙
11/27/2022
Dynamic Kernel Sparsifiers
A geometric graph associated with a set of points P= {x_1, x_2, ⋯, x_n }...
research
∙
11/20/2021
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Longest common subsequence (𝖫𝖢𝖲) is a classic and central problem in com...
research
∙
10/29/2021
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
We provide universally-optimal distributed graph algorithms for (1+ε)-ap...
research
∙
12/31/2020
Minor Sparsifiers and the Distributed Laplacian Paradigm
We study distributed algorithms built around edge contraction based vert...
research
∙
08/14/2020
On the Hardness of Massively Parallel Computation
We investigate whether there are inherent limits of parallelization in t...
research
∙
04/16/2020
Fully Dynamic c-Edge Connectivity in Subpolynomial Time
We present a deterministic fully dynamic algorithm for c-edge connectivi...
research
∙
03/16/2020
Approximating LCS in Linear Time: Beating the √(n) Barrier
Longest common subsequence (LCS) is one of the most fundamental problems...
research
∙
03/05/2020
Fast Noise Removal for k-Means Clustering
This paper considers k-means clustering in the presence of noise. It is ...
research
∙
10/25/2019
Massively Parallel Algorithms for String Matching with Wildcards
We study distributed algorithms for string matching problem in presence ...
research
∙
08/06/2019
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
In this paper we study the problem of dynamically maintaining graph prop...
research
∙
05/08/2018
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
A fundamental question that shrouds the emergence of massively parallel ...
research
∙
05/19/2017
Linear regression without correspondence
This article considers algorithmic and statistical aspects of linear reg...
research
∙
05/14/2013