4 papers
A Simple Average-case Analysis of Recursive Randomized Greedy MIS
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan MitroviÄ
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, Yamamo…
Privacy Amplification by Structured Subsampling for Deep Differentially Private Time Series Forecasting
Jan Schuchardt, Mina Dalirrooyfard, Jed Guzelkabaagac +3
Many forms of sensitive data, such as web traffic, mobility data, or hospital occupancy, are inherently sequential. The standard method for training machine learning models while e…
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…