48 citations · 79 across the 36 of their papers we have counts for
4 papers · 1 filter
Streaming Euclidean MST to a Constant Factor
Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram +2
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an -point set .…
Estimation of Entropy in Constant Space with Improved Sample Complexity
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson +1
Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy of a distribution over an alphabet of size up to additive error by streaming…
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
Moses Charikar, Erik Waingarten
We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing recent results which only applied to center-based clustering [MMR19]…
Polylogarithmic Sketches for Clustering
Moses Charikar, Erik Waingarten
Given points in , we consider the problem of partitioning points into clusters with associated centers. The cost of a clustering is the sum of pow…