57 citations · 245 across the 48 of their papers we have counts for
58 papers
Embedding Probability Distributions into Low Dimensional : Tree Ising Models via Truncated Metrics
Moses Charikar, Spencer Compton, Chirag Pabbaraju
Given an arbitrary set of high dimensional points in , there are known negative results that preclude the possibility of always mapping them to a low dimensional s…
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…
Simple, Scalable and Effective Clustering via One-Dimensional Projections
Moses Charikar, Monika Henzinger, Lunjia Hu +2
Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and -means+…
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…
Breaking the Metric Voting Distortion Barrier
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang +1
We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with voters and candidates located in a shared metric spac…
Distortion in metric matching with ordinal preferences
Nima Anari, Moses Charikar, Prasanna Ramakrishnan
Suppose that we have agents and items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their match…