23 citations · 85 across the 22 of their papers we have counts for
5 papers · 1 filter
Optimal Fully Dynamic -Centers Clustering
MohammadHossein Bateni, Hossein Esfandiari, Rajesh Jayaram +1
We present the first algorithm for fully dynamic -centers clustering in an arbitrary metric space that maintains an optimal approximation in $O(k \cdot \operatorname{polyl…
New Streaming Algorithms for High Dimensional EMD and MST
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an -point set , and com…
Truly Perfect Samplers for Data Streams and Sliding Windows
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In the -sampling problem, the goal is to output an index of a vector , such that for all coordinates , \[\textbf{Pr}[i=j] = (1 \pm ε) \frac{G(f…
In-Database Regression in Input Sparsity Time
Rajesh Jayaram, Alireza Samadian, David P. Woodruff +1
Sketching is a powerful dimensionality reduction technique for accelerating algorithms for data analysis. A crucial step in sketching methods is to compute a subspace embedding (SE…
An Optimal Algorithm for Triangle Counting in the Stream
Rajesh Jayaram, John Kallaugher
We present a new algorithm for approximating the number of triangles in a graph whose edges arrive as an arbitrary order stream. If is the number of edges in , the n…