Vincent Cohen-Addad

224 papers A* 89A 9B 3Journal 118Unranked 5

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	A Strong Linear Programming Relaxation for Weighted Tree Augmentation. CoRR Vincent Cohen-Addad, Marina Drygala, Nathan Klein, Ola Svensson
2026	J	`jnl`	Accelerating Scientific Research with Gemini: Case Studies and Common Techniques. CoRR David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Brânzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik C. S., Ken-ichi Kawarabayashi, Ravi Kumar, Silvio Lattanzi, Euiwoong Lee, Yi Li, Ioannis Panageas, Dimitris Paparas, Benjamin Przybocki, Bernardo Subercaseaux, Ola Svensson, Shayan Taherijam, Xuan Wu, Eylon Yogev, Morteza Zadimoghaddam, Samson Zhou, Yossi Matias, James Manyika, Vahab Mirrokni
2026	J	`jnl`	Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces. CoRR Vincent Cohen-Addad, Karthik C. S., David Saulpic, Chris Schwiegelshohn
2026	A*	`conf`	An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the k-Means Problem. SODA Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian
2026	J	`jnl`	Distributed Algorithms for Euclidean Clustering. CoRR Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou
2026	J	`jnl`	Near-Optimal Bounds for Parameterized Euclidean k-means. CoRR Vincent Cohen-Addad, Karthik C. S., David Saulpic, Chris Schwiegelshohn
2026	J	`jnl`	Solving an Open Problem in Theoretical Physics using AI-Assisted Discovery. CoRR Michael P. Brenner, Vincent Cohen-Addad, David P. Woodruff
2025	J	`jnl`	A (2+ ϵ)-Approximation Algorithm for Metric CoRR Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, Ola Svensson
2025	A*	`conf`	A (2+ε)-Approximation Algorithm for Metric k-Median. STOC Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, Ola Svensson
2025	A*	`conf`	A Tight VC-Dimension Analysis of Clustering Coresets with Applications. SODA Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn
2025	J	`jnl`	A Tight VC-Dimension Analysis of Clustering Coresets with Applications. CoRR Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn
2025	J	`jnl`	Algorithmic Thinking Theory. CoRR MohammadHossein Bateni, Vincent Cohen-Addad, Yuzhou Gu, Silvio Lattanzi, Simon Meierhans, Christopher Mohri
2025	A*	`conf`	Algorithms and Hardness for Active Learning on Graphs. ICML Vincent Cohen-Addad, Silvio Lattanzi, Simon Meierhans
2025	A*	`conf`	Almost Optimal PAC Learning for k-Means. STOC Vincent Cohen-Addad, Silvio Lattanzi, Chris Schwiegelshohn
2025	J	`jnl`	An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the CoRR Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian
2025	A*	`conf`	An Improved Greedy Approximation for (Metric) k-Means. FOCS Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Ernest van Wijland
2025	A*	`conf`	Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair. FOCS Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten
2025	J	`jnl`	Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair. CoRR Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten
2025	J	`jnl`	Combinatorial Optimization using Comparison Oracles. CoRR Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff
2025	B	`conf`	Complexity of Local Search for CSPs Parameterized by Constraint Difference. IPEC Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, Sijin Peng
2025	J	`jnl`	Complexity of Local Search for CSPs Parameterized by Constraint Difference. CoRR Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, Sijin Peng
2025	A*	`conf`	Correlation Clustering Beyond the Pivot Algorithm. ICML Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2025	J	`jnl`	Efficient Data Selection at Scale via Influence Distillation. CoRR Mahdi Nikdan, Vincent Cohen-Addad, Dan Alistarh, Vahab Mirrokni
2025	A*	`conf`	Embedding Planar Graphs into Graphs of Treewidth SODA Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
2025	A*	`conf`	Fair Clustering in the Sliding Window Model. ICLR Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Qiaoyuan Yang, Yubo Zhang, Samson Zhou
2025	J	`jnl`	Fair Clustering in the Sliding Window Model. CoRR Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Qiaoyuan Yang, Yubo Zhang, Samson Zhou
2025	J	`jnl`	Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings. CoRR Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou
2025	J	`jnl`	Fitting Metrics and Ultrametrics with Minimum Disagreements. SIAM J. Comput. Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
2025	J	`jnl`	How to DP-fy Your Data: A Practical Guide to Generating Synthetic Data With Differential Privacy. CoRR Natalia Ponomareva, Zheng Xu, H. Brendan McMahan, Peter Kairouz, Lucas Rosenblatt, Vincent Cohen-Addad, Cristóbal Guzmán, Ryan McKenna, Galen Andrew, Alex Bie, Da Yu, Alex Kurakin, Morteza Zadimoghaddam, Sergei Vassilvitskii, Andreas Terzis
2025	J	`jnl`	Less is More: Adaptive Coverage for Synthetic Training Data. CoRR Sasan Tavakkol, Max Springer, Mohammad Hossein Bateni, Neslihan Bulut, Vincent Cohen-Addad, MohammadTaghi Hajiaghayi
2025	A*	`conf`	Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams. COLT Ainesh Bakshi, Vincent Cohen-Addad, Rajesh Jayaram, Sam Hopkins, Silvio Lattanzi
2025	J	`jnl`	Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams. CoRR Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie, Samson Zhou
2025	J	`jnl`	Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs. SIAM J. Comput. Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk
2025	J	`jnl`	Private Training & Data Generation by Clustering Embeddings. CoRR Felix Zhou, Samson Zhou, Vahab Mirrokni, Alessandro Epasto, Vincent Cohen-Addad
2025	A*	`conf`	REINFORCE Adversarial Attacks on Large Language Models: An Adaptive, Distributional, and Semantic Objective. ICML Simon Geisler, Tom Wollschläger, M. H. I. Abdalla, Vincent Cohen-Addad, Johannes Gasteiger, Stephan Günnemann
2025	J	`jnl`	REINFORCE Adversarial Attacks on Large Language Models: An Adaptive, Distributional, and Semantic Objective. CoRR Simon Geisler, Tom Wollschläger, M. H. I. Abdalla, Vincent Cohen-Addad, Johannes Gasteiger, Stephan Günnemann
2025	J	`jnl`	SYNAPSE-G: Bridging Large Language Models and Graph Learning for Rare Event Classification. CoRR Sasan Tavakkol, Lin Chen, Max Springer, Abigail Schantz, Blaz Bratanic, Vincent Cohen-Addad, MohammadHossein Bateni
2025	A*	`conf`	Scalable Private Partition Selection via Adaptive Weighting. ICML Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam
2025	J	`jnl`	Scalable Private Partition Selection via Adaptive Weighting. CoRR Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam
2025	J	`jnl`	Scalable contribution bounding to achieve privacy. CoRR Vincent Cohen-Addad, Alessandro Epasto, Jason Lee, Morteza Zadimoghaddam
2025	A*	`conf`	Solving the Correlation Cluster LP in Sublinear Time. STOC Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
2025	J	`jnl`	Solving the Correlation Cluster LP in Sublinear Time. CoRR Nairen Cao, Vincent Cohen-Addad, Shi Li, Euiwoong Lee, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
2025	J	`jnl`	Static to Dynamic Correlation Clustering. CoRR Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
2025	A*	`conf`	The Geometry of Refusal in Large Language Models: Concept Cones and Representational Independence. ICML Tom Wollschläger, Jannes Elstner, Simon Geisler, Vincent Cohen-Addad, Stephan Günnemann, Johannes Gasteiger
2025	J	`jnl`	The Geometry of Refusal in Large Language Models: Concept Cones and Representational Independence. CoRR Tom Wollschläger, Jannes Elstner, Simon Geisler, Vincent Cohen-Addad, Stephan Günnemann, Johannes Gasteiger
2024	J	`jnl`	A 2-approximation for the bounded treewidth sparsest cut problem in sfFPT Time. Math. Program. Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
2024	A*	`conf`	A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering. ICML Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
2024	J	`jnl`	A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering. CoRR Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
2024	A*	`conf`	A PTAS for SODA Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
2024	J	`jnl`	A Scalable Algorithm for Individually Fair K-means Clustering. CoRR MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi
2024	A	`conf`	A Scalable Algorithm for Individually Fair k-Means Clustering. AISTATS MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi
2024	A*	`conf`	Combinatorial Correlation Clustering. STOC Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
2024	J	`jnl`	Combinatorial Correlation Clustering. CoRR Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
2024	A*	`conf`	Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. ICML Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
2024	J	`jnl`	Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. CoRR Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
2024	A*	`conf`	Dynamic Correlation Clustering in Sublinear Update Time. ICML Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
2024	J	`jnl`	Dynamic Correlation Clustering in Sublinear Update Time. CoRR Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
2024	J	`jnl`	Embedding Planar Graphs into Graphs of Treewidth O(log CoRR Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
2024	J	`jnl`	Fairness of linear regression in decision making. Int. J. Data Sci. Anal. Vincent Cohen-Addad, Surya Teja Gavva, Karthik C. S., Claire Mathieu, Namrata
2024	J	`jnl`	Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. J. ACM Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
2024	J	`jnl`	Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2024	A*	`conf`	Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems. NeurIPS Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi
2024	J	`jnl`	Max-Cut with ε-Accurate Predictions. CoRR Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi
2024	A*	`conf`	Multi-View Stochastic Block Models. ICML Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser
2024	J	`jnl`	Multi-View Stochastic Block Models. CoRR Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser
2024	A*	`conf`	Perturb-and-Project: Differentially Private Similarities and Marginals. ICML Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong
2024	J	`jnl`	Perturb-and-Project: Differentially Private Similarities and Marginals. CoRR Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong
2024	—	`conf`	Re-Invoke: Tool Invocation Rewriting for Zero-Shot Tool Retrieval. EMNLP (Findings) Yanfei Chen, Jinsung Yoon, Devendra Singh Sachan, Qingze Wang, Vincent Cohen-Addad, MohammadHossein Bateni, Chen-Yu Lee, Tomas Pfister
2024	J	`jnl`	Re-Invoke: Tool Invocation Rewriting for Zero-Shot Tool Retrieval. CoRR Yanfei Chen, Jinsung Yoon, Devendra Singh Sachan, Qingze Wang, Vincent Cohen-Addad, MohammadHossein Bateni, Chen-Yu Lee, Tomas Pfister
2024	A	`conf`	Recent Progress on Correlation Clustering: From Local Algorithms to Better Approximation Algorithms and Back (Invited Talk). ESA Vincent Cohen-Addad
2024	A*	`conf`	Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. FOCS Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn
2024	J	`jnl`	Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. CoRR Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn
2024	J	`jnl`	Understanding the Cluster LP for Correlation Clustering. CoRR Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
2024	A*	`conf`	Understanding the Cluster Linear Program for Correlation Clustering. STOC Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
2023	J	`jnl`	A Linear-Time ACM Trans. Algorithms Karl Bringmann, Vincent Cohen-Addad, Debarati Das
2023	J	`jnl`	A PTAS for 𝓁 CoRR Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
2023	J	`jnl`	A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies. CoRR Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi
2023	A*	`conf`	Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to SODA Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
2023	A*	`conf`	Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. FOCS Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
2023	J	`jnl`	Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. CoRR Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
2023	A*	`conf`	Differentially Private Hierarchical Clustering with Provable Approximation Guarantees. ICML Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni
2023	J	`jnl`	Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees. CoRR Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni
2023	A	`conf`	Graph Searching with Predictions. ITCS Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li
2023	A*	`conf`	Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. FOCS Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
2023	J	`jnl`	Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. CoRR Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman
2023	A*	`conf`	Multi-Swap k-Means++. NeurIPS Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis
2023	J	`jnl`	Multi-Swap k-Means++. CoRR Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis
2023	A	`conf`	On Complexity of 1-Center in Various Metrics. APPROX/RANDOM Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
2023	—	`conf`	On the Fine-Grained Complexity of Approximating SOSA Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2023	A*	`conf`	Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. FOCS Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
2023	J	`jnl`	Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. CoRR Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
2023	A*	`conf`	Private estimation algorithms for stochastic block models and mixture models. NeurIPS Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
2023	J	`jnl`	Private estimation algorithms for stochastic block models and mixture models. CoRR Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
2023	J	`jnl`	Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018). SIAM J. Comput. Elette Boyle, Vincent Cohen-Addad, Alexandra Kolla, Mikkel Thorup
2023	A*	`conf`	Streaming Euclidean MST to a Constant Factor. STOC Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten
2023	A*	`conf`	Streaming Euclidean k-median and k-means with o(log n) Space. FOCS Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
2023	J	`jnl`	Streaming Euclidean k-median and k-means with o(log n) Space. CoRR Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
2022	B	`conf`	A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time. IPCO Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
2022	A*	`conf`	A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees. PODC Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic
2022	A*	`conf`	An Improved Local Search Algorithm for k-Median. SODA Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic
2022	J	`jnl`	Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy. CoRR Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin, Varun Kanade, Frederik Mallmann-Trenn
2022	J	`jnl`	Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. CoRR Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn
2022	A*	`conf`	Bypassing the surface embedding: approximation schemes for network design in minor-free graphs. STOC Vincent Cohen-Addad
2022	A*	`conf`	Community Recovery in the Degree-Heterogeneous Stochastic Block Model. COLT Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic
2022	A*	`conf`	Correlation Clustering with Sherali-Adams. FOCS Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
2022	J	`jnl`	Correlation Clustering with Sherali-Adams. CoRR Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
2022	A*	`conf`	Fitting Metrics and Ultrametrics with Minimum Disagreements. FOCS Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
2022	J	`jnl`	Fitting Metrics and Ultrametrics with Minimum Disagreements. CoRR Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay
2022	J	`jnl`	Graph Searching with Predictions. CoRR Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li
2022	A*	`conf`	Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. ICALP Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2022	J	`jnl`	Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2022	J	`jnl`	Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. CoRR Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
2022	A*	`conf`	Improved Coresets for Euclidean k-Means. NeurIPS Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
2022	J	`jnl`	Improved Coresets for Euclidean k-Means. CoRR Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
2022	A*	`conf`	Improved approximations for Euclidean STOC Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan
2022	A*	`conf`	Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓ SODA Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2022	A*	`conf`	Massively Parallel k-Means Clustering for Perturbation Resilient Instances. ICML Vincent Cohen-Addad, Vahab S. Mirrokni, Peilin Zhong
2022	A*	`conf`	Near-Optimal Correlation Clustering with Privacy. NeurIPS Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
2022	J	`jnl`	Near-Optimal Correlation Clustering with Privacy. CoRR Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
2022	A*	`conf`	Near-Optimal Private and Scalable $k$-Clustering. NeurIPS Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong
2022	A	`conf`	On Facility Location Problem in the Local Differential Privacy Model. AISTATS Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboardi, Shi Li, Di Wang
2022	J	`jnl`	On the Fixed-Parameter Tractability of Capacitated Clustering. CoRR Vincent Cohen-Addad, Jason Li
2022	A*	`conf`	Online and Consistent Correlation Clustering. ICML Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
2022	A*	`conf`	Scalable Differentially Private Clustering via Hierarchically Separated Trees. KDD Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Muñoz Medina, David Saulpic, Chris Schwiegelshohn, Sergei Vassilvitskii
2022	J	`jnl`	Scalable Differentially Private Clustering via Hierarchically Separated Trees. CoRR Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab S. Mirrokni, Andres Muñoz Medina, David Saulpic, Chris Schwiegelshohn, Sergei Vassilvitskii
2022	J	`jnl`	Streaming Euclidean MST to a Constant Factor. CoRR Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2022	A*	`conf`	The Power of Uniform Sampling for Coresets. FOCS Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
2022	J	`jnl`	The Power of Uniform Sampling for Coresets. CoRR Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
2022	J	`jnl`	Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
2022	A*	`conf`	Towards optimal lower bounds for k-median and k-means coresets. STOC Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
2021	J	`jnl`	A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time. CoRR Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
2021	J	`jnl`	A Linear-Time n CoRR Karl Bringmann, Vincent Cohen-Addad, Debarati Das
2021	J	`jnl`	A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals. SIAM J. Comput. Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
2021	J	`jnl`	A New Coreset Framework for Clustering. CoRR Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
2021	J	`jnl`	A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
2021	A*	`conf`	A new coreset framework for clustering. STOC Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
2021	A*	`conf`	A quasipolynomial (2 + STOC Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
2021	J	`jnl`	Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. J. ACM Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay
2021	J	`jnl`	An Improved Local Search Algorithm for k-Median. CoRR Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic
2021	A*	`conf`	Correlation Clustering in Constant Many Parallel Rounds. ICML Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
2021	J	`jnl`	Correlation Clustering in Constant Many Parallel Rounds. CoRR Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
2021	A*	`conf`	Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. FOCS Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
2021	J	`jnl`	Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. CoRR Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
2021	A*	`conf`	Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. NeurIPS Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
2021	A*	`conf`	Improving Ultrametrics Embeddings Through Coresets. ICML Vincent Cohen-Addad, Rémi de Joannis de Verclos, Guillaume Lagarde
2021	J	`jnl`	Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics. Electron. Colloquium Comput. Complex. Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2021	J	`jnl`	Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. CoRR Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2021	J	`jnl`	Mitigating COVID-19 outbreaks in workplaces and schools by hybrid telecommuting. PLoS Comput. Biol. Simon Mauras, Vincent Cohen-Addad, Guillaume Duboc, Max Dupré la Tour, Paolo Frasca, Claire Mathieu, Lulla Opatowski, Laurent Viennot
2021	J	`jnl`	Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. J. ACM Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic
2021	A*	`conf`	On Approximability of Clustering Problems Without Candidate Centers. SODA Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2021	J	`jnl`	On Complexity of 1-Center in Various Metrics. CoRR Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
2021	—	`conf`	On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. FORC Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram
2021	A	`conf`	Online k-means Clustering. AISTATS Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
2021	A*	`conf`	Parallel and Efficient Hierarchical k-Median Clustering. NeurIPS Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson
2020	A*	`conf`	Approximation Schemes for Capacitated Clustering in Doubling Metrics. SODA Vincent Cohen-Addad
2020	A*	`conf`	Fast and Accurate $k$-means++ via Rejection Sampling. NeurIPS Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson
2020	J	`jnl`	Fast and Accurate k-means++ via Rejection Sampling. CoRR Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson
2020	A*	`conf`	Instance-Optimality in the Noisy Value-and Comparison-Model. SODA Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
2020	J	`jnl`	New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020	A*	`conf`	New hardness results for planar graph problems in p and an algorithm for sparsest cut. STOC Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020	J	`jnl`	On Approximability of Clustering Problems Without Candidate Centers. CoRR Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2020	A*	`conf`	On Efficient Low Distortion Ultrametric Embedding. ICML Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
2020	J	`jnl`	On Efficient Low Distortion Ultrametric Embedding. CoRR Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
2020	A*	`conf`	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. FOCS Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
2020	J	`jnl`	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. CoRR Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
2020	A*	`conf`	On the Power of Louvain in the Stochastic Block Model. NeurIPS Vincent Cohen-Addad, Adrian Kosowski, Frederik Mallmann-Trenn, David Saulpic
2020	J	`jnl`	On the computational tractability of a geographic clustering problem arising in redistricting. CoRR Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
2019	A*	`conf`	A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. FOCS Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk
2019	J	`jnl`	A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. CoRR Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk
2019	A*	`conf`	Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. SoCG Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay
2019	J	`jnl`	Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. CoRR Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay
2019	A	`conf`	Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. ESA Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk
2019	J	`jnl`	Efficient approximation schemes for uniform-cost clustering problems in planar graphs. CoRR Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk
2019	A*	`conf`	Fully Dynamic Consistent Facility Location. NeurIPS Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, Chris Schwiegelshohn
2019	J	`jnl`	Hierarchical Clustering: Objective Functions and Algorithms. J. ACM Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
2019	A*	`conf`	Inapproximability of Clustering in Lp Metrics. FOCS Vincent Cohen-Addad, Karthik C. S.
2019	J	`jnl`	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2019	A*	`conf`	Lower bounds for text indexing with mismatches and differences. SODA Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
2019	A*	`conf`	Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics. FOCS David Saulpic, Vincent Cohen-Addad, Andreas Emil Feldmann
2019	A*	`conf`	Oblivious dimension reduction for STOC Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, Chris Schwiegelshohn
2019	A*	`conf`	On the Fixed-Parameter Tractability of Capacitated Clustering. ICALP Vincent Cohen-Addad, Jason Li
2019	J	`jnl`	Online k-means Clustering. CoRR Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom
2019	A*	`conf`	Subquadratic High-Dimensional Hierarchical Clustering. NeurIPS Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge
2019	J	`jnl`	Tight FPT Approximations for $k$-Median and k-Means. CoRR Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li
2019	A*	`conf`	Tight FPT Approximations for k-Median and k-Means. ICALP Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li
2018	A*	`conf`	A Fast Approximation Scheme for Low-Dimensional SODA Vincent Cohen-Addad
2018	A*	`conf`	A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals. SODA Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
2018	J	`jnl`	Approximation Schemes for Capacitated Clustering in Doubling Metrics. CoRR Vincent Cohen-Addad
2018	—	`conf`	Balanced centroidal power diagrams for redistricting. SIGSPATIAL/GIS Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
2018	A*	`conf`	Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms. NeurIPS Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
2018	J	`jnl`	Fast Fencing. CoRR Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup
2018	A*	`conf`	Fast fencing. STOC Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup
2018	A*	`conf`	Hierarchical Clustering: Objective Functions and Algorithms. SODA Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
2018	J	`jnl`	Instance-Optimality in the Noisy Value-and Comparison-Model - Accept, Accept, Strong Accept: Which Papers get in? CoRR Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
2018	J	`jnl`	Lower bounds for text indexing with mismatches and differences. CoRR Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
2018	J	`jnl`	Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics. CoRR Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic
2018	A*	`conf`	The Bane of Low-Dimensionality Clustering. SODA Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman
2017	J	`jnl`	A Fast Approximation Scheme for Low-Dimensional k-Means. CoRR Vincent Cohen-Addad
2017	J	`jnl`	Balanced power diagrams for redistricting. CoRR Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
2017	A*	`conf`	Fast and Compact Exact Distance Oracle for Planar Graphs. FOCS Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen
2017	J	`jnl`	Fast and Compact Exact Distance Oracle for Planar Graphs. CoRR Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen
2017	—	`conf`	Hierarchical Clustering Beyond the Worst-Case. NIPS Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
2017	J	`jnl`	Hierarchical Clustering: Objective Functions and Algorithms. CoRR Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu
2017	A*	`conf`	On the Local Structure of Stable Clustering Instances. FOCS Vincent Cohen-Addad, Chris Schwiegelshohn
2017	J	`jnl`	One Size Fits All : Effectiveness of Local Search on Structured Data. CoRR Vincent Cohen-Addad, Chris Schwiegelshohn
2017	A	`conf`	Online Optimization of Smoothed Piecewise Constant Functions. AISTATS Vincent Cohen-Addad, Varun Kanade
2017	J	`jnl`	Steinberg's Conjecture is false. J. Comb. Theory B Vincent Cohen-Addad, Michael Hebdige, Daniel Král', Zhentao Li, Esteban Salgado
2017	J	`jnl`	The Bane of Low-Dimensionality Clustering. CoRR Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman
2016	J	`jnl`	A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals. CoRR Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
2016	J	`jnl`	Algorithmic aspects of switch cographs. Discret. Appl. Math. Vincent Cohen-Addad, Michel Habib, Fabien de Montgolfier
2016	A*	`conf`	Approximating connectivity domination in weighted bounded-genus graphs. STOC Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld
2016	A*	`conf`	Diameter and k-Center in Sliding Windows. ICALP Vincent Cohen-Addad, Chris Schwiegelshohn, Christian Sohler
2016	A*	`conf`	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2016	J	`jnl`	Online Optimization of Smoothed Piecewise Constant Functions. CoRR Vincent Cohen-Addad, Varun Kanade
2016	A*	`conf`	The Invisible Hand of Dynamic Market Pricing. EC Vincent Cohen-Addad, Alon Eden, Michal Feldman, Amos Fiat
2016	J	`jnl`	The power of local search for clustering. CoRR Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2015	A	`conf`	A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface. ESA Vincent Cohen-Addad, Arnaud de Mesmay
2015	J	`jnl`	A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface. CoRR Vincent Cohen-Addad, Arnaud de Mesmay
2015	A*	`conf`	Effectiveness of Local Search for Geometric Optimization. SoCG Vincent Cohen-Addad, Claire Mathieu
2015	J	`jnl`	The Invisible Hand of Dynamic Market Pricing. CoRR Vincent Cohen-Addad, Alon Eden, Michal Feldman, Amos Fiat
2014	B	`conf`	Energy-Efficient Algorithms for Non-preemptive Speed-Scaling. WAOA Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis
2014	J	`jnl`	Energy-efficient algorithms for non-preemptive speed-scaling. CoRR Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis
2014	J	`jnl`	The Unreasonable Success of Local Search: Geometric Optimization. CoRR Vincent Cohen-Addad, Claire Mathieu
2013	J	`jnl`	Algorithmic Aspects of Switch Cographs. CoRR Vincent Cohen-Addad, Michel Habib, Fabien de Montgolfier