default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDVincent Cohen-Addad
Person information
- affiliation: Google Zurich, Switzerland
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j13]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): 337-347 (2024)- [j12]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): 10:1-10:41 (2024) - [j11]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): 479-495 (2024) - [c87]MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi:
A Scalable Algorithm for Individually Fair k-Means Clustering. AISTATS 2024: 3151-3159 - [c86]Vincent Cohen-Addad:
Recent Progress on Correlation Clustering: From Local Algorithms to Better Approximation Algorithms and Back (Invited Talk). ESA 2024: 1:1-1:2 - [c85]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. ICML 2024 - [c84]Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis:
Dynamic Correlation Clustering in Sublinear Update Time. ICML 2024 - [c83]Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong:
Perturb-and-Project: Differentially Private Similarities and Marginals. ICML 2024 - [c82]Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser:
Multi-View Stochastic Block Models. ICML 2024 - [c81]Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar:
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering. ICML 2024 - [c80]Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang:
A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals. SODA 2024: 935-961 - [c79]Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl:
Understanding the Cluster Linear Program for Correlation Clustering. STOC 2024: 1605-1616 - [c78]Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang:
Combinatorial Correlation Clustering. STOC 2024: 1617-1628 - [i75]MohammadHossein Bateni, Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi:
A Scalable Algorithm for Individually Fair K-means Clustering. CoRR abs/2402.06730 (2024) - [i74]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 abs/2402.17327 (2024) - [i73]Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi:
Max-Cut with ε-Accurate Predictions. CoRR abs/2402.18263 (2024) - [i72]Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang:
Combinatorial Correlation Clustering. CoRR abs/2404.05433 (2024) - [i71]Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma:
Fully Dynamic Correlation Clustering: Breaking 3-Approximation. CoRR abs/2404.06797 (2024) - [i70]Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl:
Understanding the Cluster LP for Correlation Clustering. CoRR abs/2404.17509 (2024) - [i69]Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn:
Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. CoRR abs/2405.01339 (2024) - [i68]Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar:
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering. CoRR abs/2406.04857 (2024) - [i67]Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser:
Multi-View Stochastic Block Models. CoRR abs/2406.04860 (2024) - [i66]Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong:
Perturb-and-Project: Differentially Private Similarities and Marginals. CoRR abs/2406.04868 (2024) - [i65]Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis:
Dynamic Correlation Clustering in Sublinear Update Time. CoRR abs/2406.09137 (2024) - [i64]Yanfei Chen, Jinsung Yoon, Devendra Singh Sachan, Qingze Wang, Vincent Cohen-Addad, MohammadHossein Bateni, Chen-Yu Lee, Tomas Pfister:
Re-Invoke: Tool Invocation Rewriting for Zero-Shot Tool Retrieval. CoRR abs/2408.01875 (2024) - 2023
- [j10]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): S18- (2023) - [j9]Karl Bringmann, Vincent Cohen-Addad, Debarati Das:
A Linear-Time n0.4-Approximation for Longest Common Subsequence. ACM Trans. Algorithms 19(1): 9:1-9:24 (2023) - [c77]Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM 2023: 1:1-1:19 - [c76]Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS 2023: 883-908 - [c75]Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman:
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. FOCS 2023: 1082-1104 - [c74]Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. FOCS 2023: 1105-1130 - [c73]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: 2262-2277 - [c72]Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni:
Differentially Private Hierarchical Clustering with Provable Approximation Guarantees. ICML 2023: 14353-14375 - [c71]Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li:
Graph Searching with Predictions. ITCS 2023: 12:1-12:24 - [c70]Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis:
Multi-Swap k-Means++. NeurIPS 2023 - [c69]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 - [c68]Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn:
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. SODA 2023: 940-986 - [c67]Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs. SOSA 2023: 145-155 - [c66]Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten:
Streaming Euclidean MST to a Constant Factor. STOC 2023: 156-169 - [i63]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 abs/2301.04822 (2023) - [i62]Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni:
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees. CoRR abs/2302.00037 (2023) - [i61]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 abs/2304.07268 (2023) - [i60]Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis:
Multi-Swap k-Means++. CoRR abs/2309.16384 (2023) - [i59]Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman:
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. CoRR abs/2309.17243 (2023) - [i58]Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. CoRR abs/2310.02882 (2023) - [i57]Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. CoRR abs/2310.04076 (2023) - [i56]Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang:
A PTAS for 𝓁0-Low Rank Approximation: Solving Dense CSPs over Reals. CoRR abs/2311.00892 (2023) - [i55]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 abs/2311.17840 (2023) - 2022
- [c65]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: 3914-3929 - [c64]Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic:
Community Recovery in the Degree-Heterogeneous Stochastic Block Model. COLT 2022: 1662-1692 - [c63]Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay:
Fitting Metrics and Ultrametrics with Minimum Disagreements. FOCS 2022: 301-311 - [c62]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: 462-473 - [c61]Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman:
Correlation Clustering with Sherali-Adams. FOCS 2022: 651-661 - [c60]Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. ICALP 2022: 7:1-7:18 - [c59]Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis:
Online and Consistent Correlation Clustering. ICML 2022: 4157-4179 - [c58]Vincent Cohen-Addad, Vahab S. Mirrokni, Peilin Zhong:
Massively Parallel k-Means Clustering for Perturbation Resilient Instances. ICML 2022: 4180-4201 - [c57]Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo:
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time. IPCO 2022: 112-125 - [c56]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: 221-230 - [c55]Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong:
Near-Optimal Private and Scalable $k$-Clustering. NeurIPS 2022 - [c54]Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski:
Near-Optimal Correlation Clustering with Privacy. NeurIPS 2022 - [c53]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar:
Improved Coresets for Euclidean k-Means. NeurIPS 2022 - [c52]Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic:
A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees. PODC 2022: 356-365 - [c51]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics. SODA 2022: 1493-1530 - [c50]Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic:
An Improved Local Search Algorithm for k-Median. SODA 2022: 1556-1612 - [c49]Vincent Cohen-Addad:
Bypassing the surface embedding: approximation schemes for network design in minor-free graphs. STOC 2022: 343-356 - [c48]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn:
Towards optimal lower bounds for k-median and k-means coresets. STOC 2022: 1038-1051 - [c47]Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan:
Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. STOC 2022: 1621-1628 - [i54]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn:
Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR abs/2202.12793 (2022) - [i53]Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski:
Near-Optimal Correlation Clustering with Privacy. CoRR abs/2203.01440 (2022) - [i52]Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi:
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR abs/2203.01857 (2022) - [i51]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 abs/2204.04828 (2022) - [i50]Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin, Varun Kanade, Frederik Mallmann-Trenn:
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy. CoRR abs/2205.12327 (2022) - [i49]Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab S. Mirrokni, Andres Muñoz Medina, David Saulpic, Chris Schwiegelshohn, Sergei Vassilvitskii:
Scalable Differentially Private Clustering via Hierarchically Separated Trees. CoRR abs/2206.08646 (2022) - [i48]Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn:
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. CoRR abs/2207.05150 (2022) - [i47]Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman:
Correlation Clustering with Sherali-Adams. CoRR abs/2207.10889 (2022) - [i46]Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay:
Fitting Metrics and Ultrametrics with Minimum Disagreements. CoRR abs/2208.13920 (2022) - [i45]Vincent Cohen-Addad, Jason Li:
On the Fixed-Parameter Tractability of Capacitated Clustering. CoRR abs/2208.14129 (2022) - [i44]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 abs/2209.01901 (2022) - [i43]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar:
Improved Coresets for Euclidean k-Means. CoRR abs/2211.08184 (2022) - [i42]Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
Streaming Euclidean MST to a Constant Factor. CoRR abs/2212.06546 (2022) - [i41]Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li:
Graph Searching with Predictions. CoRR abs/2212.14220 (2022) - 2021
- [j8]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): 30:1-30:26 (2021) - [j7]Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic:
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. J. ACM 68(6): 44:1-44:34 (2021) - [j6]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) - [j5]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): 1-31 (2021) - [c46]Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom:
Online k-means Clustering. AISTATS 2021: 1126-1134 - [c45]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: 468-479 - [c44]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: 3:1-3:18 - [c43]Vincent Cohen-Addad, Rémi de Joannis de Verclos, Guillaume Lagarde:
Improving Ultrametrics Embeddings Through Coresets. ICML 2021: 2060-2068 - [c42]Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski:
Correlation Clustering in Constant Many Parallel Rounds. ICML 2021: 2069-2078 - [c41]Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson:
Parallel and Efficient Hierarchical k-Median Clustering. NeurIPS 2021: 20333-20345 - [c40]Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. NeurIPS 2021: 21085-21098 - [c39]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
On Approximability of Clustering Problems Without Candidate Centers. SODA 2021: 2635-2648 - [c38]Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
A new coreset framework for clustering. STOC 2021: 169-182 - [c37]Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A quasipolynomial (2 + ε)-approximation for planar sparsest cut. STOC 2021: 1056-1069 - [i40]Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
A New Coreset Framework for Clustering. CoRR abs/2104.06133 (2021) - [i39]Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR abs/2105.15187 (2021) - [i38]Karl Bringmann, Vincent Cohen-Addad, Debarati Das:
A Linear-Time n0.4-Approximation for Longest Common Subsequence. CoRR abs/2106.08195 (2021) - [i37]Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski:
Correlation Clustering in Constant Many Parallel Rounds. CoRR abs/2106.08448 (2021) - [i36]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 abs/2110.02807 (2021) - [i35]Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic:
An Improved Local Search Algorithm for k-Median. CoRR abs/2111.04589 (2021) - [i34]Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo:
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time. CoRR abs/2111.06163 (2021) - [i33]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. CoRR abs/2111.10912 (2021) - [i32]Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. CoRR abs/2112.03222 (2021) - [i31]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. TR21 (2021) - 2020
- [c36]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: 589-600 - [c35]Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde:
On Efficient Low Distortion Ultrametric Embedding. ICML 2020: 2078-2088 - [c34]Vincent Cohen-Addad, Adrian Kosowski, Frederik Mallmann-Trenn, David Saulpic:
On the Power of Louvain in the Stochastic Block Model. NeurIPS 2020 - [c33]Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson:
Fast and Accurate $k$-means++ via Rejection Sampling. NeurIPS 2020 - [c32]Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu:
Instance-Optimality in the Noisy Value-and Comparison-Model. SODA 2020: 2124-2143 - [c31]Vincent Cohen-Addad:
Approximation Schemes for Capacitated Clustering in Doubling Metrics. SODA 2020: 2241-2259 - [c30]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: 996-1009 - [i30]Amir Abboud, Vincent Cohen-Addad, Philip N. Klein:
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR abs/2007.02377 (2020) - [i29]Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde:
On Efficient Low Distortion Ultrametric Embedding. CoRR abs/2008.06700 (2020) - [i28]Vincent Cohen-Addad, Philip N. Klein, Dániel Marx:
On the computational tractability of a geographic clustering problem arising in redistricting. CoRR abs/2009.00188 (2020) - [i27]Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le:
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. CoRR abs/2009.05039 (2020) - [i26]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
On Approximability of Clustering Problems Without Candidate Centers. CoRR abs/2010.00087 (2020) - [i25]Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson:
Fast and Accurate k-means++ via Rejection Sampling. CoRR abs/2012.11891 (2020)
2010 – 2019
- 2019
- [j4]Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu:
Hierarchical Clustering: Objective Functions and Algorithms. J. ACM 66(4): 26:1-26:42 (2019) - [j3]Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. 48(2): 644-667 (2019) - [c29]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. SoCG 2019: 27:1-27:16 - [c28]Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. ESA 2019: 33:1-33:14 - [c27]Vincent Cohen-Addad, Karthik C. S.:
Inapproximability of Clustering in Lp Metrics. FOCS 2019: 519-539 - [c26]David Saulpic, Vincent Cohen-Addad, Andreas Emil Feldmann:
Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics. FOCS 2019: 540-559 - [c25]Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk:
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. FOCS 2019: 560-581 - [c24]Vincent Cohen-Addad, Jason Li:
On the Fixed-Parameter Tractability of Capacitated Clustering. ICALP 2019: 41:1-41:14 - [c23]Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li:
Tight FPT Approximations for k-Median and k-Means. ICALP 2019: 42:1-42:14 - [c22]Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, Chris Schwiegelshohn:
Fully Dynamic Consistent Facility Location. NeurIPS 2019: 3250-3260 - [c21]Amir Abboud, Vincent Cohen-Addad, Hussein Houdrouge:
Subquadratic High-Dimensional Hierarchical Clustering. NeurIPS 2019: 11576-11586 - [c20]Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya:
Lower bounds for text indexing with mismatches and differences. SODA 2019: 1146-1164 - [c19]Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, Chris Schwiegelshohn:
Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. STOC 2019: 1039-1050 - [i24]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. CoRR abs/1903.08603 (2019) - [i23]Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. CoRR abs/1904.10680 (2019) - [i22]Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li:
Tight FPT Approximations for $k$-Median and k-Means. CoRR abs/1904.12334 (2019) - [i21]Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
Efficient approximation schemes for uniform-cost clustering problems in planar graphs. CoRR abs/1905.00656 (2019) - [i20]Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom:
Online k-means Clustering. CoRR abs/1909.06861 (2019) - 2018
- [c18]Vincent Cohen-Addad, Philip N. Klein, Neal E. Young:
Balanced centroidal power diagrams for redistricting. SIGSPATIAL/GIS 2018: 389-396 - [c17]Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn:
Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms. NeurIPS 2018: 8526-8535 - [c16]Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu:
Hierarchical Clustering: Objective Functions and Algorithms. SODA 2018: 378-397 - [c15]Vincent Cohen-Addad:
A Fast Approximation Scheme for Low-Dimensional k-Means. SODA 2018: 430-440 - [c14]Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman:
The Bane of Low-Dimensionality Clustering. SODA 2018: 441-456 - [c13]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. SODA 2018: 1439-1458 - [c12]Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup:
Fast fencing. STOC 2018: 564-573 - [i19]Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup:
Fast Fencing. CoRR abs/1804.00101 (2018) - [i18]Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu:
Instance-Optimality in the Noisy Value-and Comparison-Model - Accept, Accept, Strong Accept: Which Papers get in? CoRR abs/1806.08182 (2018) - [i17]Vincent Cohen-Addad:
Approximation Schemes for Capacitated Clustering in Doubling Metrics. CoRR abs/1812.07721 (2018) - [i16]Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic:
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics. CoRR abs/1812.08664 (2018) - [i15]Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya:
Lower bounds for text indexing with mismatches and differences. CoRR abs/1812.09120 (2018) - 2017
- [j2]Vincent Cohen-Addad, Michael Hebdige, Daniel Král', Zhentao Li, Esteban Salgado:
Steinberg's Conjecture is false. J. Comb. Theory B 122: 452-456 (2017) - [c11]Vincent Cohen-Addad, Varun Kanade:
Online Optimization of Smoothed Piecewise Constant Functions. AISTATS 2017: 412-420 - [c10]Vincent Cohen-Addad, Chris Schwiegelshohn:
On the Local Structure of Stable Clustering Instances. FOCS 2017: 49-60 - [c9]Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen:
Fast and Compact Exact Distance Oracle for Planar Graphs. FOCS 2017: 962-973 - [c8]Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn:
Hierarchical Clustering Beyond the Worst-Case. NIPS 2017: 6201-6209 - [i14]Vincent Cohen-Addad, Chris Schwiegelshohn:
One Size Fits All : Effectiveness of Local Search on Structured Data. CoRR abs/1701.08423 (2017) - [i13]Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen:
Fast and Compact Exact Distance Oracle for Planar Graphs. CoRR abs/1702.03259 (2017) - [i12]Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu:
Hierarchical Clustering: Objective Functions and Algorithms. CoRR abs/1704.02147 (2017) - [i11]Vincent Cohen-Addad:
A Fast Approximation Scheme for Low-Dimensional k-Means. CoRR abs/1708.07381 (2017) - [i10]Vincent Cohen-Addad, Philip N. Klein, Neal E. Young:
Balanced power diagrams for redistricting. CoRR abs/1710.03358 (2017) - [i9]Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman:
The Bane of Low-Dimensionality Clustering. CoRR abs/1711.01171 (2017) - 2016
- [j1]Vincent Cohen-Addad, Michel Habib, Fabien de Montgolfier:
Algorithmic aspects of switch cographs. Discret. Appl. Math. 200: 23-42 (2016) - [c7]Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS 2016: 353-364 - [c6]Vincent Cohen-Addad, Chris Schwiegelshohn, Christian Sohler:
Diameter and k-Center in Sliding Windows. ICALP 2016: 19:1-19:12 - [c5]Vincent Cohen-Addad, Alon Eden, Michal Feldman, Amos Fiat:
The Invisible Hand of Dynamic Market Pricing. EC 2016: 383-400 - [c4]Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld:
Approximating connectivity domination in weighted bounded-genus graphs. STOC 2016: 584-597 - [i8]Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
The power of local search for clustering. CoRR abs/1603.09535 (2016) - [i7]Vincent Cohen-Addad, Varun Kanade:
Online Optimization of Smoothed Piecewise Constant Functions. CoRR abs/1604.01999 (2016) - [i6]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. CoRR abs/1611.02966 (2016) - 2015
- [c3]Vincent Cohen-Addad, Claire Mathieu:
Effectiveness of Local Search for Geometric Optimization. SoCG 2015: 329-343 - [c2]Vincent Cohen-Addad, Arnaud de Mesmay:
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface. ESA 2015: 386-398 - [i5]Vincent Cohen-Addad, Arnaud de Mesmay:
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface. CoRR abs/1507.01688 (2015) - [i4]Vincent Cohen-Addad, Alon Eden, Michal Feldman, Amos Fiat:
The Invisible Hand of Dynamic Market Pricing. CoRR abs/1511.05646 (2015) - 2014
- [c1]Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis:
Energy-Efficient Algorithms for Non-preemptive Speed-Scaling. WAOA 2014: 107-118 - [i3]Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis:
Energy-efficient algorithms for non-preemptive speed-scaling. CoRR abs/1402.4111 (2014) - [i2]Vincent Cohen-Addad, Claire Mathieu:
The Unreasonable Success of Local Search: Geometric Optimization. CoRR abs/1410.0553 (2014) - 2013
- [i1]Vincent Cohen-Addad, Michel Habib, Fabien de Montgolfier:
Algorithmic Aspects of Switch Cographs. CoRR abs/1310.1012 (2013)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-28 21:15 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
