15 citations · 35 across the 17 of their papers we have counts for
26 papers · 1 filter
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…
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…
Almost 3-Approximate Correlation Clustering in Constant Rounds
Soheil Behnezhad, Moses Charikar, Weiyun Ma +1
We study parallel algorithms for correlation clustering. Each pair among objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbit…
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…
Multiway Online Correlated Selection
Guy Blanc, Moses Charikar
We give a -competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was due to Fahrbach, Huang, Tao, and Za…