57 citations · 245 across the 48 of their papers we have counts for
3 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…
Relax, no need to round: integrality of clustering formulations
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar +3
We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering:…