AIConfPaper
← Search

Slobodan Mitrović

9 accepted papers

2025

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal +1
ICML 2025poster

We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^…

Cited by 0Source ↗PDF ↗Scholar ↗
2025

Differentially Private Gomory-Hu Trees

Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal +1
NeurIPS 2025poster

Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ that preserves the Min-$s$-$t$-Cut between any pair of vertices $s, t \in V$. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clus…

Cited by 0Source ↗Scholar ↗
2025

New Parallel and Streaming Algorithms for Directed Densest Subgraph

Slobodan Mitrović, Theodore Pan, Mahdi Qaempanah, Mohammad Amin Raeisi
NeurIPS 2025poster

Finding dense subgraphs is a fundamental problem with applications to community detection, clustering, and data mining. Our work focuses on finding approximate densest subgraphs in directed graphs in computational models for processing massive data. We consider two such models: Massively Parallel Co…

Cited by 0Source ↗Scholar ↗
2025

Sparse-pivot: Dynamic correlation clustering for node insertions

Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
ICML 2025spotlight

We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new no…

Cited by 0Source ↗PDF ↗Scholar ↗
2021

Correlation Clustering in Constant Many Parallel Rounds

Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
ICML 2021oral

Correlation clustering is a central topic in unsupervised learning, with many applications in ML and data mining. In correlation clustering, one receives as input a signed graph and the goal is to partition it to minimize the number of disagreements. In this work we propose a massively parallel comp…

Cited by 48Source ↗PDF ↗Scholar ↗
2020

Fairness in Streaming Submodular Maximization: Algorithms and Hardness

Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos, Jakub M Tarnawski
NeurIPS 2020poster

Submodular maximization has become established as the method of choice for the task of selecting representative and diverse summaries of data. However, if datapoints have sensitive attributes such as gender or age, such machine learning algorithms, left unchecked, are known to exhibit bias: under- o…

Cited by 59Source ↗PDF ↗code ↗Scholar ↗
2020

Fully Dynamic Algorithm for Constrained Submodular Optimization

Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub M Tarnawski, Morteza Zadimoghaddam
NeurIPS 2020oral

The task of maximizing a monotone submodular function under a cardinality constraint is at the core of many machine learning and data mining applications, including data summarization, sparse regression and coverage problems. We study this classic problem in the fully dynamic setting, where elements…

Cited by 30Source ↗PDF ↗Scholar ↗
2019

Improved Parallel Algorithms for Density-Based Network Clustering

Mohsen Ghaffari, Silvio Lattanzi, Slobodan Mitrović
ICML 2019oral

Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density, which in the literature is captured by two fundamental problems: the densest su…

Cited by 56Source ↗PDF ↗Scholar ↗
2017

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Ilija Bogunovic, Slobodan Mitrović, Jonathan Scarlett, Volkan Cevher
ICML 2017poster

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint $k$, with the added twist that a number of items $\tau$ from the returned set may be removed. We focus on the worst-case setting considered by Orlin et al.\ (2016), in which a constant-factor approx…

Cited by 77Source ↗PDF ↗Scholar ↗