Vincent Cohen-Addad

ORCID

Publication Activity (10 Years)

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

Top Venues

Publications

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, Karthik C. S., Guillaume Lagarde
On Efficient Low Distortion Ultrametric Embedding. CoRR (2020)
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. CoRR (2020)
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson
Fast and Accurate $k$-means++ via Rejection Sampling. NeurIPS (2020)
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR (2020)
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
New hardness results for planar graph problems in p and an algorithm for sparsest cut. STOC (2020)
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
On the computational tractability of a geographic clustering problem arising in redistricting. CoRR (2020)
Vincent Cohen-Addad, Adrian Kosowski, Frederik Mallmann-Trenn, David Saulpic
On the Power of Louvain in the Stochastic Block Model. NeurIPS (2020)
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. FOCS (2020)
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson
Fast and Accurate k-means++ via Rejection Sampling. CoRR (2020)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Approximability of Clustering Problems Without Candidate Centers. CoRR (2020)
Vincent Cohen-Addad
Approximation Schemes for Capacitated Clustering in Doubling Metrics. SODA (2020)
Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
On Efficient Low Distortion Ultrametric Embedding. ICML (2020)
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li
Tight FPT Approximations for $k$-Median and k-Means. CoRR (2019)
Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
Lower bounds for text indexing with mismatches and differences. SODA (2019)
Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk
Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. ESA (2019)
Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
Online k-means Clustering. CoRR (2019)
Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk
Efficient approximation schemes for uniform-cost clustering problems in planar graphs. CoRR (2019)

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

Publication Activity (10 Years)

Top Topics

Top Venues

Vincent Cohen-Addad