2 papers
cs.DS2025
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…
cs.DS2024
Differentially Private Gomory-Hu Trees
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
Given an undirected, weighted -vertex graph , a Gomory-Hu tree is a weighted tree on such that for any pair of distinct vertices , the Min-…