Vincent Cohen-Addad

ORCID

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 161

Top Venues

Publications

Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. CoRR (2024)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. J. ACM 71 (2) (2024)
Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn
Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. CoRR (2024)
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
Understanding the Cluster Linear Program for Correlation Clustering. STOC (2024)
Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser
Multi-View Stochastic Block Models. CoRR (2024)
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
Combinatorial Correlation Clustering. CoRR (2024)
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
Dynamic Correlation Clustering in Sublinear Update Time. CoRR (2024)
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi
Max-Cut with ε-Accurate Predictions. CoRR (2024)
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR (2024)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. SODA (2024)
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
Combinatorial Correlation Clustering. STOC (2024)
Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering. CoRR (2024)
MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi
A Scalable Algorithm for Individually Fair k-Means Clustering. AISTATS (2024)
Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong
Perturb-and-Project: Differentially Private Similarities and Marginals. CoRR (2024)
Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
A 2-approximation for the bounded treewidth sparsest cut problem in sfFPT Time. Math. Program. 206 (1) (2024)
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
Understanding the Cluster LP for Correlation Clustering. CoRR (2024)
Vincent Cohen-Addad, Surya Teja Gavva, Karthik C. S., Claire Mathieu, Namrata
Fairness of linear regression in decision making. Int. J. Data Sci. Anal. 18 (3) (2024)
MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi
A Scalable Algorithm for Individually Fair K-means Clustering. CoRR (2024)
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
Streaming Euclidean k-median and k-means with o(log n) Space. CoRR (2023)
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
-Approximation for Longest Common Subsequence. ACM Trans. Algorithms 19 (1) (2023)
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS (2023)
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
-Median. SODA (2023)
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis
Multi-Swap k-Means++. NeurIPS (2023)
Elette Boyle, Vincent Cohen-Addad, Alexandra Kolla, Mikkel Thorup
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018). SIAM J. Comput. 52 (6) (2023)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
-Center in Sparse Graphs. SOSA (2023)
Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees. CoRR (2023)
Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni
Differentially Private Hierarchical Clustering with Provable Approximation Guarantees. ICML (2023)
Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. FOCS (2023)
Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. CoRR (2023)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. CoRR (2023)
Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li
Graph Searching with Predictions. ITCS (2023)
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. CoRR (2023)
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. FOCS (2023)
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. FOCS (2023)
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
Private estimation algorithms for stochastic block models and mixture models. NeurIPS (2023)
Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi
A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies. CoRR (2023)
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis
Multi-Swap k-Means++. CoRR (2023)
Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten
Streaming Euclidean MST to a Constant Factor. STOC (2023)
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
Private estimation algorithms for stochastic block models and mixture models. CoRR (2023)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM (2023)
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. CoRR (2023)
Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li
Graph Searching with Predictions. CoRR (2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. ICALP (2022)
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic
An Improved Local Search Algorithm for k-Median. SODA (2022)
Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
Near-Optimal Correlation Clustering with Privacy. NeurIPS (2022)
Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic
Community Recovery in the Degree-Heterogeneous Stochastic Block Model. COLT (2022)
Vincent Cohen-Addad
Bypassing the surface embedding: approximation schemes for network design in minor-free graphs. STOC (2022)
Vincent Cohen-Addad, Jason Li
On the Fixed-Parameter Tractability of Capacitated Clustering. CoRR (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
Towards optimal lower bounds for k-median and k-means coresets. STOC (2022)
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
Fitting Metrics and Ultrametrics with Minimum Disagreements. FOCS (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
Improved Coresets for Euclidean k-Means. NeurIPS (2022)
Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
Streaming Euclidean MST to a Constant Factor. CoRR (2022)
Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic
A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees. PODC (2022)
Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab S. Mirrokni, Andres Munoz, David Saulpic, Chris Schwiegelshohn, Sergei Vassilvitskii
Scalable Differentially Private Clustering via Hierarchically Separated Trees. CoRR (2022)
Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Muñoz Medina, David Saulpic, Chris Schwiegelshohn, Sergei Vassilvitskii
Scalable Differentially Private Clustering via Hierarchically Separated Trees. KDD (2022)
Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboardi, Shi Li, Di Wang
On Facility Location Problem in the Local Differential Privacy Model. AISTATS (2022)
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. CoRR (2022)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. FOCS (2022)
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. CoRR (2022)
Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin, Varun Kanade, Frederik Mallmann-Trenn
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy. CoRR (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR (2022)
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
Online and Consistent Correlation Clustering. ICML (2022)
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
The Power of Uniform Sampling for Coresets. FOCS (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
Improved Coresets for Euclidean k-Means. CoRR (2022)
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
Correlation Clustering with Sherali-Adams. CoRR (2022)
Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong
Near-Optimal Private and Scalable $k$-Clustering. NeurIPS (2022)
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
The Power of Uniform Sampling for Coresets. CoRR (2022)
Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
Near-Optimal Correlation Clustering with Privacy. CoRR (2022)
Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time. IPCO (2022)
Vincent Cohen-Addad, Vahab S. Mirrokni, Peilin Zhong
Massively Parallel k-Means Clustering for Perturbation Resilient Instances. ICML (2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR (2022)
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
-median, via nested quasi-independent sets. STOC (2022)
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
Correlation Clustering with Sherali-Adams. FOCS (2022)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
-metrics. SODA (2022)
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
Fitting Metrics and Ultrametrics with Minimum Disagreements. CoRR (2022)
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
A new coreset framework for clustering. STOC (2021)
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram
On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. FORC (2021)
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
-Approximation for Longest Common Subsequence. CoRR (2021)
Simon Mauras, Vincent Cohen-Addad, Guillaume Duboc, Max Dupré la Tour, Paolo Frasca, Claire Mathieu, Lulla Opatowski, Laurent Viennot
Mitigating COVID-19 outbreaks in workplaces and schools by hybrid telecommuting. PLoS Comput. Biol. 17 (8) (2021)
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
A New Coreset Framework for Clustering. CoRR (2021)
Vincent Cohen-Addad, Rémi de Joannis de Verclos, Guillaume Lagarde
Improving Ultrametrics Embeddings Through Coresets. ICML (2021)
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. J. ACM 68 (4) (2021)
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. NeurIPS (2021)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. CoRR (2021)
Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
Correlation Clustering in Constant Many Parallel Rounds. CoRR (2021)
Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
Online k-means Clustering. AISTATS (2021)
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
)-approximation for planar sparsest cut. STOC (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. CoRR (2021)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. CoRR (2021)
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic
An Improved Local Search Algorithm for k-Median. CoRR (2021)
Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time. CoRR (2021)
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR (2021)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. FOCS (2021)
Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. J. ACM 68 (6) (2021)
Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals. SIAM J. Comput. 50 (1) (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Approximability of Clustering Problems Without Candidate Centers. SODA (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics. Electron. Colloquium Comput. Complex. 28 (2021)
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson
Parallel and Efficient Hierarchical k-Median Clustering. NeurIPS (2021)
Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
Correlation Clustering in Constant Many Parallel Rounds. ICML (2021)
Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
Instance-Optimality in the Noisy Value-and Comparison-Model. SODA (2020)

Vincent Cohen-Addad.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Vincent Cohen-Addad