About

Slobodan Mitrovic is an Assistant Professor in the Department of Computer Science at UC Davis, with a guest professor position in the Department of Mathematics and Informatics at the University of Novi Sad. His academic background includes a PhD from the Computer Science department at EPFL, where he was advised by Aleksander Mądry. Prior to his current position, he was a Postdoctoral Fellow at the Theory of Computation group at MIT's CSAIL, hosted by Ronitt Rubinfeld, and spent two months at ETH hosted by Mohsen Ghaffari. His research broadly focuses on algorithmic graph theory and the combinatorial approach to optimization, with particular emphasis on designing efficient algorithms for memory-constrained computation environments such as parallel, distributed, streaming, and local computation models. His work has been supported by the NSF CAREER program and Google Research Scholar Program. Mitrovic is actively involved in the academic community through program committees for major conferences and organizing algorithmic puzzle events. He also teaches courses related to algorithm design and analysis, and special topics in computer science theory.

Research topics

• Computer Science
• Algorithm
• Mathematics
• Artificial Intelligence
• Parallel computing
• Mathematics education
• Theoretical computer science
• Combinatorics
• Discrete mathematics
• Psychology
• Mathematical optimization

Selected publications

• A Simple Average-case Analysis of Recursive Randomized Greedy MIS

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapterSenior author

  We revisit the complexity analysis of the recursive version of the randomized greedy algorithm for computing a maximal independent set (MIS), originally analyzed by Yoshida, Yamamoto, and Ito (2009). They showed that, on average per vertex, the expected number of recursive calls made by this algorithm is upperbounded by the average degree of the input graph. While their analysis is clever and intricate, we provide a significantly simpler alternative that achieves the same guarantee.

  PublisherDOI

• Approximate Counting of Permutation Patterns

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter

  We consider the problem of counting the copies of a length-\(k\) pattern \(\sigma\) in a sequence \(f : [n] \to \mathbb{R}\), where a copy is a subset of indices \(i_1 \lt \dots \lt i_k \in [n]\) such that \(f(i_j) \lt f(i_\ell)\) if and only if \(\sigma(j) \lt \sigma(\ell)\). This problem is motivated by a range of connections and applications in ranking, nonparametric statistics, combinatorics, and fine-grained complexity, especially when \(k\) is a small fixed constant.

  PublisherDOI

• Locally computing edge orientations

  arXiv (Cornell University) · 2025-01-03

  preprintOpen access1st authorCorresponding

  We consider the question of orienting the edges in a graph $G$ such that every vertex has bounded out-degree. For graphs of arboricity $α$, there is an orientation in which every vertex has out-degree at most $α$ and, moreover, the best possible maximum out-degree of an orientation is at least $α- 1$. We are thus interested in algorithms that can achieve a maximum out-degree of close to $α$. A widely studied approach for this problem in the distributed algorithms setting is a ``peeling algorithm'' that provides an orientation with maximum out-degree $α(2+ε)$ in a logarithmic number of iterations. We consider this problem in the local computation algorithm (LCA) model, which quickly answers queries of the form ``What is the orientation of edge $(u,v)$?'' by probing the input graph. When the peeling algorithm is executed in the LCA setting by applying standard techniques, e.g., the Parnas-Ron paradigm, it requires $Ω(n)$ probes per query on an $n$-vertex graph. In the case where $G$ has unbounded degree, we show that any LCA that orients its edges to yield maximum out-degree $r$ must use $Ω(\sqrt n/r)$ probes to $G$ per query in the worst case, even if $G$ is known to be a forest (that is, $α=1$). We also show several algorithms with sublinear probe complexity when $G$ has unbounded degree. When $G$ is a tree such that the maximum degree $Δ$ of $G$ is bounded, we demonstrate an algorithm that uses $Δn^{1-\log_Δr + o(1)}$ probes to $G$ per query. To obtain this result, we develop an edge-coloring approach that ultimately yields a graph-shattering-like result. We also use this shattering-like approach to demonstrate an LCA which $4$-colors any tree using sublinear probes per query.

  PublisherOA PDFDOI

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

  ArXiv.org · 2025-07-02

  preprintOpen access

  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^{1.5})$ additive error and $1+γ$ multiplicative error for any $γ> 0$ [Gupta, Roth, Ullman TCC'12]. In contrast, "inefficient" algorithms, i.e., those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+γ$ multiplicative error [Eli{á}{š}, Kapralov, Kulkarni, Lee SODA'20]. In this work, we break the $n^{1.5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon,δ)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+γ$ and additive error $n^{1.25 + o(1)}$ (ignoring dependencies on $\varepsilon, δ, γ$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

  PublisherOA PDFDOI

• MOGUĆNOST PRIMENE TEHNIKE ZA OBLIKOVANJE SAOBRAĆAJA ZASNOVANE NA UPOTREBI SAVREMENIH SKRIPTING REŠENJA

  2025-11-26

  article1st authorCorresponding
  PublisherDOI

• Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models

  arXiv (Cornell University) · 2024-02-24

  preprintOpen accessSenior author

  Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and within-cluster negative edges. This problem has many applications in data mining, particularly in unsupervised learning. Inspired by the prevalence of large graphs and constantly changing data in modern applications, we study correlation clustering in dynamic, parallel (MPC), and local computation (LCA) settings. We design an approach that improves state-of-the-art runtime complexities in all these settings. In particular, we provide the first fully dynamic algorithm that runs in an expected amortized constant time, without any dependence on the graph size. Moreover, our algorithm essentially matches the approximation guarantee of the celebrated Pivot algorithm.

  PublisherOA PDFDOI

• Differentially Private Gomory-Hu Trees

  arXiv (Cornell University) · 2024-08-03

  preprintOpen access

  Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-Hu tree is a well-studied problem in graph algorithms and has received considerable attention. In particular, a long line of work recently culminated in constructing a Gomory-Hu tree in almost linear time [Abboud, Li, Panigrahi and Saranurak, FOCS 2023]. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s, t \in V$ with high probability. Our error bound is essentially optimal, as [Dalirrooyfard, Mitrović and Nevmyvaka, NeurIPS 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $Ω(n)$ additive error even with $(1, 0.1)$-DP and allowing for a multiplicative error term. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth and Ullman, TCC 2012] and $O(\sqrt{mn} \cdot \text{polylog}(n/δ) / \varepsilon)$ for $(\varepsilon, δ)$-DP [Liu, Upadhyay and Zou, SODA 2024], both of which are implied by differential private algorithms that preserve all cuts in the graph. An important technical ingredient of our main result is an $\varepsilon$-DP algorithm for computing minimum Isolating Cuts with $\tilde{O}(n / \varepsilon)$ additive error, which may be of independent interest.

  PublisherOA PDFDOI

• Network traffic control using traffic shaping techniques

  Tehnika · 2024-01-01

  articleOpen accessSenior author

  Although known for years, the problem of meeting network traffic demand in multiservice environment is still recognized as one of the most significant challenges, regardless of the constant increase in network infrastructure capacity. One of the most important causes of this problem is the bursty nature of network traffic that could reflect on the network efficiency reduction due to temporal congestion of network resources. In this way, the operational characteristics of certain business systems as well as the quality of residential internet/iptv services could be compromised. One of the standard approaches to solving such a kind of problems is related to the concept of traffic management that includes 1) Traffic Policing techniques, as well as 2) Traffic Shaping techniques. Although these techniques share the same conceptual basis, these techniques also have significant differences, due to which they achieve different effects on network traffic. The importance of Traffic Shaping techniques arise with their potential to manage the traffic quality in modern network forms, such as Internet of Things (IoT) sensor networks. This paper explains the basic concept of traffic shaping, available algorithms on which traffic shaping techniques are based and provides a comparison with Traffic Policing techniques.

  PublisherOA PDFDOI

• Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling

  arXiv (Cornell University) · 2024-01-01 · 3 citations

  preprintOpen accessSenior author

  The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there are two standard guarantees: an O(log Δ)-approximation (where Δ is the maximum set size) and an O(f)-approximation (where f is the maximum number of sets containing any given element). In this paper, we introduce a new, surprisingly simple, model-independent approach to solving SetCover in unweighted graphs. We obtain multiple improved algorithms in the MPC and CRCW PRAM models. First, in the MPC model with sublinear space per machine, our algorithms can compute an O(f) approximation to SetCover in Ô(√{log Δ} + log f) rounds and a O(log Δ) approximation in O(log^{3/2} n) rounds. Moreover, in the PRAM model, we give a O(f) approximate algorithm using linear work and O(log n) depth. All these bounds improve the existing round complexity/depth bounds by a log^{Ω(1)} n factor. Moreover, our approach leads to many other new algorithms, including improved algorithms for the HypergraphMatching problem in the MPC model, as well as simpler SetCover algorithms that match the existing bounds.

  PublisherOA PDFDOI

• Dynamic PageRank: Algorithms and Lower Bounds

  arXiv (Cornell University) · 2024-04-25

  preprintOpen access

  We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector $π\in \mathbb{R}^n$ for a graph under a sequence of edge insertions and deletions. Our main result is a complete characterization of the complexity of dynamic PageRank maintenance for both multiplicative and additive ($L_1$) approximations. First, we establish matching lower and upper bounds for maintaining additive approximate PageRank in both incremental and decremental settings. In particular, we demonstrate that in the worst-case $(1/α)^{Θ(\log \log n)}$ update time is necessary and sufficient for this problem, where $α$ is the desired additive approximation. On the other hand, we demonstrate that the commonly employed ForwardPush approach performs substantially worse than this optimal runtime. Specifically, we show that ForwardPush requires $Ω(n^{1-δ})$ time per update on average, for any $δ> 0$, even in the incremental setting. For multiplicative approximations, however, we demonstrate that the situation is significantly more challenging. Specifically, we prove that any algorithm that explicitly maintains a constant factor multiplicative approximation of the PageRank vector of a directed graph must have amortized update time $Ω(n^{1-δ})$, for any $δ> 0$, even in the incremental setting, thereby resolving a 13-year old open question of Bahmani et al.~(VLDB 2010). This sharply contrasts with the undirected setting, where we show that $\rm{poly}\ \log n$ update time is feasible, even in the fully dynamic setting under oblivious adversary.

  PublisherOA PDFDOI

Frequent coauthors

• Rajko Jović

  University of Novi Sad

  19 shared

• Ashkan Norouzi-Fard

  Google (Switzerland)

  16 shared

• Valentina Dz. Radojicic

  14 shared

• Jakub Tarnawski

  Microsoft (United States)

  13 shared

• Ronitt Rubinfeld

  Massachusetts Institute of Technology

  11 shared

• Jakub Łącki

  Google (United States)

  10 shared

• Mila Veselinović

  University of Novi Sad

  10 shared

• Mohsen Ghaffari

  9 shared

Labs

• Slobodan Mitrovic LabPI

Education

• Ph.D., Computer Science

  EPFL

• Other, Theory of Computation

  MIT

• Other

  ETH

Awards & honors

• Homometric sets in diameter-two and outerplanar graphs IEEE…