57 citations · 245 across the 48 of their papers we have counts for
6 papers · 1 filter
A Characterization of List Learnability
Moses Charikar, Chirag Pabbaraju
A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass se…
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur +1
We provide an efficient unified plug-in approach for estimating symmetric properties of distributions given independent samples. Our estimator is based on profile-maximum-likel…
On the Complexity of Sampling Redistricting Plans
Moses Charikar, Paul Liu, Tianyu Liu +1
A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination…
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…
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…