6 citations · 10 across the 5 of their papers we have counts for
6 papers · 1 filter
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
Moses Charikar, Michael Kapralov, Erik Waingarten
In the kernel density estimation (KDE) problem one is given a kernel and a dataset of points in a Euclidean space, and must prepare a data structure that can quickly…
Improved Approximations for Ultrametric Violation Distance
Moses Charikar, Ruiquan Gao
We study the Ultrametric Violation Distance problem introduced by Cohen-Addad, Fan, Lee, and Mesmay [FOCS, 2022]. Given pairwise distances a…
Fast Algorithms for a New Relaxation of Optimal Transport
Moses Charikar, Beidi Chen, Christopher Re +1
We introduce a new class of objectives for optimal transport computations of datasets in high-dimensional Euclidean spaces. The new objectives are parametrized by , and pr…
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
Moses Charikar, Vaggos Chatziafratis
Dasgupta recently introduced a cost function for the hierarchical clustering of a set of points given pairwise similarities between them. He showed that this function is NP-hard to…
Online Bipartite Matching with Decomposable Weights
Moses Charikar, Monika Henzinger, Huy L. Nguyen
We study a weighted online bipartite matching problem: is a weighted bipartite graph where is known beforehand and the vertices of arrive online. The g…
Vertex Sparsifiers and Abstract Rounding Algorithms
Moses Charikar, Tom Leighton, Shi Li +1
The notion of vertex sparsification is introduced in \cite{M}, where it was shown that for any graph and a subset of terminals , there is a polynomial…