6 papers
Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications
Slobodan Mitrović, Theodore Pan, Wen-Horng Sheu
A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This para…
Dynamic Construction of the Lovász Local Lemma
Bernhard Haeupler, Slobodan MitroviÄ, Srikkanth Ramachandran +2
This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized number of…
Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Slobodan MitroviÄ, Srikkanth Ramachandran, Ronitt Rubinfeld +1
In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for comput…
New Parallel and Streaming Algorithms for Directed Densest Subgraph
Slobodan MitroviÄ, Theodore Pan, Mahdi Qaempanah +1
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…
Breaking the Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been mad…
SPARSE-PIVOT: Dynamic correlation clustering for node insertions
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan MitroviÄ
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 Parotsi…