57 citations · 245 across the 48 of their papers we have counts for
10 papers · 1 filter
Kernel Density Estimation through Density Constrained Near Neighbor Search
Moses Charikar, Michael Kapralov, Navid Nouri +1
In this paper we revisit the kernel density estimation problem: given a kernel and a dataset of points in high dimensional Euclidean space, prepare a data structure t…
Instance Based Approximations to Profile Maximum Likelihood
Nima Anari, Moses Charikar, Kirankumar Shiragur +1
In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimat…
Distributed Algorithms from Arboreal Ants for the Shortest Path Problem
Shivam Garg, Kirankumar Shiragur, Deborah M. Gordon +1
Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants…
Improved Algorithms for Edge Colouring in the W-Streaming Model
Moses Charikar, Paul Liu
In the W-streaming model, an algorithm is given space and must process a large graph of up to edges. In this short note we give two algorithms fo…
Nearest Neighbor Search for Hyperbolic Embeddings
Xian Wu, Moses Charikar
Embedding into hyperbolic space is emerging as an effective representation technique for datasets that exhibit hierarchical structure. This development motivates the need for algor…
A Simple Sublinear Algorithm for Gap Edit Distance
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
We study the problem of estimating the edit distance between two -character strings. While exact computation in the worst case is believed to require near-quadratic time, previo…