9 papers
An Efficient Private Algorithm for Community Detection
Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan +2
In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exac…
Retriever Portfolios: A Principled Approach to Adaptive RAG
Miltiadis Stouras, Vincent Cohen-Addad, Silvio Lattanzi +1
Retrieval-augmented generation (RAG) systems typically rely on a single retriever and a single set of hyperparameters, despite facing highly heterogeneous queries that range from s…
Algorithmic Thinking Theory
MohammadHossein Bateni, Vincent Cohen-Addad, Yuzhou Gu +3
Large language models (LLMs) have proven to be highly effective for solving complex reasoning tasks. Surprisingly, their capabilities can often be improved by iterating on previous…
Almost Optimal Fully Dynamic -Center Clustering with Recourse
Sayan Bhattacharya, MartÃn Costa, Ermiya Farokhnejad +2
In this paper, we consider the \emph{metric -center} problem in the fully dynamic setting, where we are given a metric space evolving via a sequence of point insertions…
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2
Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…
Multi-Swap -Means++
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi +1
The -means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular -means clustering objective and is know…