6 papers
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
We give a new dual fitting algorithm which gives improved approximation ratios of and for -Means in (high-dimensional) Euclidean and genera…
An Improved Greedy Approximation for (Metric) -Means
Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao +3
Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the -Means…
Dynamic Data Layout Optimization with Worst-case Guarantees
Kexin Rong, Paul Liu, Sarah Ashok Sonje +1
Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve…
Quantifying the Gain in Weak-to-Strong Generalization
Moses Charikar, Chirag Pabbaraju, Kirankumar Shiragur
Recent advances in large language models have shown capabilities that are extraordinary and near-superhuman. These models operate with such complexity that reliably evaluating and…
Correlation Clustering Beyond the Pivot Algorithm
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad +2
We study the classic correlation clustering in the dynamic setting. Given objects and a complete labeling of the object-pairs as either similar or dissimilar, the goal is to pa…
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
Moses Charikar, Michael Kapralov, Erik Waingarten
In the kernel density estimation (KDE) problem one is given a kernel and a dataset of points in a Euclidean space, and must prepare a data structure that can quickly…