Research

Conferences:

• Almost Optimal Fully Dynamic k-Center Clustering with Recourse
  S. Bhattacharya, M. Costa, E. Farokhnejad, S. Lattanzi, N. Parotsidis
  ICML 2025

• Algorithms and Hardness for Active Learning on Graphs
  V. Cohen-Addad, S. Lattanzi, S. Meierhans
  ICML 2025

• Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
  A. Bakshi, V. Cohen-Addad, S. Hopkins, R. Jayaram, S. Lattanzi
  COLT 2025 [pdf]

• Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
  M. Kapralov, A. Kumar, S. Lattanzi, A. Mousavifar, W. Wrzos-Kaminska
  ICALP 2025 [pdf]

• Almost Optimal PAC Learning for k-Means

V. Cohen-Addad, S. Lattanzi, C. Schwiegelshohn
STOC 2025 [pdf]

• The Cost of Consistency: Submodular Maximization with Constant Recourse

P. Duetting, F. Fusco, S. Lattanzi, A. Norouzi Fard, O. Svensson, M. Zadimoghaddam
STOC 2025 [pdf]

• Data-Driven Solution Portfolios
  M. Drygala, S. Lattanzi, A. Maggiori, M. Stouras, O. Svensson, S. Vassilvitskii
  ITCS 2025 [pdf]

• Almost Tight Bounds for Differentially Private Densest Subgraph
  M. Dinitz, S. Kale, S. Lattanzi and S. Vassilvitskii
  SODA 2025 [pdf]

• Fully Dynamic k-clustering with Fast Update Time and Small Recourse
  S. Bhattacharya, M. Costa, N. Garg, S. Lattanzi and N. Parotsidis
  FOCS 2024 [pdf]

• Resilient K-Clustering
  S. Ahmadian, M. Bateni, H. Esfandiari, S. Lattanzi, M. Monemizadeh and A. Norouzi-Fard
  KDD 2024 [pdf]

• Multi-View Stochastic Block Models
  V. Cohen-Addad, T. D'Orsi, S. Lattanzi and R. Nasser
  ICML 2024 [pdf]

• Dynamic Correlation Clustering in Sublinear Update Time
  V. Cohen-Addad, S. Lattanzi, A. Maggiori and N. Parotsidis
  ICML 2024 [pdf]

• Consistent Submodular Maximization
  P. Dütting, F. Fusco, S. Lattanzi, A. Norouzi-Fard, M. Zadimoghaddam
  ICML 2024 [pdf]

• A Scalable Algorithm for Individually Fair K-means Clustering
  M. Bateni, V. Cohen-Addad, A. Epasto, S. Lattanzi
  AISTATS 2024 [pdf]

• Multi-Swap k-Means++
  L. Beretta, V. Cohen-Addad, S. Lattanzi, N. Parotsidis
  NeurIPS 2023 [pdf]

• Fully Dynamic k-clustering in Õ(k) Update Time
  S. Bhattacharya, M. Costa, S. Lattanzi, N. Parotsidis
  NeurIPS 2023 [pdf]

• Fully Dynamic Submodular Maximization over Matroids
  P. Dütting, F. Fusco, S. Lattanzi, A. Norouzi-Fard, M. Zadimoghaddam
  ICML 2023 [pdf]

• Speeding Up Bellman Ford via Minimum Violation Permutations
  S. Lattanzi, O. Svensson, S. Vassilvitskii
  ICML 2023 [pdf]

• Learning Hierarchical Cluster Structure of Graphs in Sublinear Time
  M. Kapralov, A. Kumar, S. Lattanzi and A. Mousavifar
  SODA 2023 [pdf]

• Efficient and Stable Fully Dynamic Facility Location
  S. Bhattacharya, S. Lattanzi and N. Parotsidis
  NeurIPS 2022 [pdf]

• Active Learning of Classifiers with Label and Seed Queries
  M. Bressan, N. Cesa-Bianchi, S. Lattanzi, A. Paudice and  M.  Thiessen
  NeurIPS 2022 [pdf]

• Near–Optimal Correlation Clustering with Privacy
  V. Cohen-Addad, C. Fan, S. Lattanzi, S. Mitrović, A. Norouzi-Fard, N. Parotsidis and J. Tarnawski
  NeurIPS 2022 [pdf]

• Approximate Cluster Recovery from Noisy Labels
  B. Gamlath, S. Lattanzi, A. Norouzi-Fard and O. Svensson
  COLT 2022 [pdf]

• Deletion Robust Submodular Maximization over Matroids
  P. Duetting, F. Fusco, S. Lattanzi, A. Norouzi-Fard and M. Zadimoghaddam
  ICML 2022 [pdf]

• Online and Consistent Correlation Clustering
  V. Cohen-Addad, S. Lattanzi, A. Maggiori and N. Parotsidis
  ICML 2022 [pdf]

• Scalable Differentially Private Clustering via Hierarchically Separated Trees
  V. Cohen-Addad, A. Epasto, S. Lattanzi,  V. Mirrokni, A. Munoz Medina, D. Saulpic, C. Schwiegelshohn and S. Vassilvitskii
  KDD 2022 [pdf]

• The Gibbs--Rand Model
  F.  Chierichetti, R. Kumar and S. Lattanzi
  PODS 2022 [pdf]

• Parallel and Efficient Hierarchical k-Median Clustering
  V. Cohen-Addad, S. Lattanzi, A. Norouzi-Fard, C. Sohler and O. Svensson
  NeurIPS 2021 [pdf]

• Efficient and Local Parallel Random Walks
  M. Kapralov, S. Lattanzi, N. Nouri and J. Tardos
  NeurIPS 2021 [pdf]

• Online Facility Location with Multiple Advice
  M. Almanza, F. Chierichetti, S. Lattanzi, A. Panconesi and G. Re
  NeurIPS 2021 [pdf]

• Robust Online Correlation Clustering
  S. Lattanzi, B. Moseley, S. Vassilvitskii, Y. Wang and R. Zhou
  NeurIPS 2021 [pdf]

• On Margin-Based Cluster Recovery with Oracle Queries
  M. Bressan, N. Cesa-Bianchi, S. Lattanzi and A. Paudice
  NeurIPS 2021 [pdf]

• Exact Recovery of Clusters in Finite Metric Spaces using Oracle Queries
  M. Bressan, N. Cesa-Bianchi, S. Lattanzi and A. Paudice
  COLT 2021 [pdf]

• Correlation Clustering in Constant Many Parallel Rounds
  V. Cohen-Addad, S. Lattanzi, S. Mitrović, A. Norouzi-Fard, N. Parotsidis and J. Tarnawski
  ICML 2021 [pdf]

• Secretaries with Advice
  P. Duetting, S. Lattanzi, R. Paes Leme, S. Vasilvistkii
  EC 2021 [pdf]

• Twin Peaks, a Model for Recurring Cascades
  M. Almanza, S. Lattanzi, A. Panconesi and G. Re
  TheWebConf 2021 [pdf]

• Spectral Clustering Oracles in Sublinear Time
  G. Gluch, M. Kapralov, S. Lattanzi, A. Mousavifar, C. Sohler
  SODA 2021 [pdf]

• Consistent k-Clustering for General Metrics
  H. Fichtenberger, S. Lattanzi, A. Norouzi-Fard, O. Svensson
  SODA 2021 [pdf]

• Fully Dynamic Algorithm for Constrained Submodular Optimization
  S. Lattanzi, S. Mitrović, A. Norouzi-Fard, J. Tarnawski, M. Zadimoghaddam
  NeurIPS 2020 (Oral) [pdf]

• Exact Recovery of Mangled Clusters with Same-Cluster Queries
  M. Bressan, N. Cesa-Bianchi, S. Lattanzi, A. Paudice
  NeurIPS 2020 (Oral) [pdf]

• Sliding Window Algorithms for k-Clustering Problems
  M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvtiskii, M. Zadimoghaddam
  NeurIPS 2020 [pdf]

• Fast and Accurate k-means++ via Rejection Sampling
  V. Cohen-Addad, S. Lattanzi, A. Norouzi-Fard, C. Sohler, O. Svensson
  NeurIPS 2020 [pdf]

• Online MAP Inference of Determinantal Point Processes
  A. Bhaskara, A. Karbasi, S. Lattanzi, M. Zadimoghaddam
  NeurIPS 2020 [pdf]

• Online Scheduling via Learned Weights
  S. Lattanzi, T. Lavastida, B. Moseley and S. Vassilvitskii
  SODA 2020 [pdf]

• Residual Based Sampling for Online Low Rank Approximation
  A. Bhaskara, S. Lattanzi, S. Vassilvitskii and M. Zadimoghaddam
  FOCS 2019 [pdf]

• A Framework for Parallelizing Hierarchical Clustering Methods
  K. Lu, T. Lavastida, S. Lattanzi and B. Moseley
  ECML PKDD 2019 [pdf]

• A Better k-means++ Algorithm via Local Search
  S. Lattanzi and C. Sohler
  ICML 2019 [pdf]

• Improved Parallel Algorithms for Density-Based Network Clustering
  M. Ghaffari, S. Lattanzi and S. Mitrovic
  ICML 2019 [pdf]

• Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
  A. Karbasi, E. Kazemi, , S. Lattanzi, M. Mitrovic and M. Zadimoghaddam
  ICML 2019 [pdf]

• Dynamic Algorithms for the Massively Parallel Computation Model
  G. Italiano, S. Lattanzi, V. Mirrokni and N. Parotsidis
  SPAA 2019 [pdf]

• Better Sliding Windows Algorithms for Subadditive and Diversity Maximization
  M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii and M. Zadimoghaddam
  PODS 2019 [pdf]

• Consistent Online Optimization: Convex and Submodular
  M. R. Karimi, A. Krause, S. Lattanzi, and S. Vassilvitskii
  AISTATS 2019 [pdf]

• Matroids, Matching, and Fairness
  F. Chierichetti, R. Kumar, S. Lattanzi and S. Vassilvitskii
  AISTATS 2019 [pdf]

• Top-k Lists: Models and Algorithms
  F. Chierichetti, A. Dasgupta, S. Haddadan, R. Kumar, S. Lattanzi
  NeurIPS 2018 [pdf]

• Parallel and Streaming Algorithms for K-Core Decomposition
  H. Esfandiari, S. Lattanzi and V. Mirrokni
  ICML 2018 [pdf]

• One-shot Coresets: The Case of K-Clustering
  O. Bachem, M. Lučić and S. Lattanzi
  AISTATS 2018 [pdf]

• Non-Negative Sparse Regression and Column Subset Selection with \ell_1 Error
  A. Bhaskara and S. Lattanzi
  ITCS 2018 [pdf]

• Fair Clustering Through Fairlets
  F. Chierichetti, R. Kumar, S. Lattanzi and S. Vassilvitskii
  NeurIPS 2017 [pdf]

• Affinity Clustering: Hierarchical Clustering at Scale
  M. Bateni, S. Behnezhad, M. Derakhshan, M. Hajiaghayi, R. Kiveris, S. Lattanzi and V. Mirrokni
  NeurIPS 2017 [pdf]

• Consistent k-clustering
  S. Lattanzi and S. Vassilvitskii
  ICML 2017 [pdf]

• Algorithms for lp Low-Rank Approximation
  F. Chierichetti, S. Gallapudi, R. Kumar, S. Lattanzi, R. Panigrahy and D. P. Woodruff
  ICML 2017 [pdf]

• Ego-splitting framework: from Non-Overalapping to Overalapping Clusters
  A. Epasto, S. Lattanzi and R. Paes Lemme
  KDD 2017 [pdf]

• Submodular Optimization over Sliding Windows
  A. Epasto, S. Lattanzi, S. Vassilvitskii and M. Zadimoghaddam
  WWW 2017 [pdf]

• Indexing Public-Private Graphs
  A. Archer, S. Lattanzi, P. Likarish and S. Vassilvitskii
  WWW 2017 [pdf]

• Community Detection on Evolving Graphs
  A. Anagnostopolous, J. Łącki, S. Lattanzi, S. Leonardi and M. Mahdian
  NeurIPS 2016 [pdf]

• Linking Users Across Domains with Location Data: Theory and Validation
  C. Riederer, Y. Kim, N. Korula, S. Lattanzi and A. Chaintreau
  WWW 2016 [pdf]

• On Sampling Nodes in a Network
  F. Chierichetti, A. Dasgupta, R. Kumar, S. Lattanzi and T. Sarlos
  WWW 2016 [pdf]

• Expander via Local Edge Flips
  Z. Allen-Zhu, A. Bhaskara, S. Lattanzi, V. Mirrokni and L. Orecchia
  SODA 2016 [pdf]

• Efficient Algorithms for Public-Private Social Networks
  A. Epasto, F. Chierichetti, R. Kumar, S. Lattanzi and V. Mirrokni
  KDD 2015 (Best Paper Award) [pdf]

• Efficient Densest Subgraph Computation in Evolving Graphs
  A. Epasto, S. Lattanzi and M. Sozio
  WWW 2015 [pdf]

• The Power of Random Neighbors in Social Networks
  S. Lattanzi and Y. Singer
  WSDM 2015 [pdf]

• On Learning Mixture Models for Permutations
  F. Chierichetti, A. Dasgupta, R. Kumar and S. Lattanzi
  ITCS 2015 [pdf]

• Robust Hierarchical k-center clustering
  S. Lattanzi, S. Leonardi, V. Mirrokni and I. Razenshteyn
  ITCS 2015 [pdf]

• Distributed Balanced Clustering via Mapping Coresets
  M. Bateni, A. Bhaskara, S. Lattanzi and V. Mirrokni
  NeurIPS 2014 [pdf]

• Connected Components in MapReduce and Beyond
  R. Kiveris, S. Lattanzi, V. Mirrokni, V. Rastogi and S. Vassilvitskii
  SOCC 2014 [pdf]

• Efficient computation of the Weighted Clustering Coefficient
  S. Lattanzi and S. Leonardi
  WAW 2014 [pdf]

• On Reconstructing a Hidden Permutation
  F. Chierichetti, A. Dasgupta, R. Kumar and S. Lattanzi
  RANDOM 2014 [pdf]

• Filter & Follow: Do Social Media Encourage Efficient News Curation?
  A. May, A. Chaintreau, N. Korula and S. Lattanzi
  SIGMETRICS 2014 [pdf]

• Reduce and Aggregate: Similarity Ranking in Multi-Categorical Bipartite Graphs.
  A. Epasto, J. Feldman, S. Lattanzi, S. Leonardi and V. Mirrokni
  WWW 2014 [pdf]

• Learning Entangled Single-Sample Gaussians.
  F. Chierichetti, A. Dasgupta, R. Kumar and S. Lattanzi
  SODA 2014 [pdf]

• A Local Algorithm for Finding Well-Connected Clusters.
  Z. A. Zhu, S. Lattanzi and V. Mirrokni
  ICML 2013 [pdf]

• Sok: The Evolution of Sybil Defense via Social Networks.
  L. Alvisi, A. Clement, A. Epasto, S. Lattanzi and A. Panconesi
  S&P 2013 [pdf]

• Arrival and departure in Social Networks.
  S. Wu, A. Das Sarma, A. Fabrikant, S. Lattanzi and A. Tomkins
  WSDM 2013 [pdf]

• Hiring a Secretary from a Poset.
  R. Kumar, S. Lattanzi, S. Vassilvitskii and A. Vattani
  EC 2011 [pdf]

• Filtering: A Method for Solving Graph Problems in MapReduce.
  S. Lattanzi, B. Moseley, S. Suri and S. Vassilvitskii
  SPAA 2011 [pdf]

• Milgram-routing in social networks.
  S. Lattanzi, A. Panconesi and D. Sivakumar
  WWW 2011 [pdf]

• An Algorithmic Treatment of Strong Queries. 
  R. Kumar, S. Lattanzi and P. Raghavan
  WSDM 2011 [pdf]

• Almost tight bounds for rumor spreading with conductance. 
  F. Chierichetti, S. Lattanzi and A. Panconesi
  STOC 2010 [pdf]

• Rumour spreading and graph conductance. 
  F. Chierichetti, S. Lattanzi and A. Panconesi
  SODA 2010 [pdf]

• Models for the Compressible Web.
  F. Chierichetti, R. Kumar, S. Lattanzi, A. Panconesi and P. Raghavan
  FOCS 2009 [pdf]

• Rumor Spreading in Social Networks.
  F. Chierichetti, S. Lattanzi and A. Panconesi
  ICALP 2009 [pdf]

• On compressing social networks.
  F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi and P. Raghavan
  KDD 2009 [pdf]

• Affiliation Networks.
  S. Lattanzi and D. Sivakumar
  STOC 2009 [pdf]

• On placing skips optimally in expectation.
  F. Chierichetti, S. Lattanzi, F. Mari and A. Panconesi
  WSDM 2008 [pdf]