{"ID":2899293,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.01873","arxiv_id":"2507.01873","title":"Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition","abstract":"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 $γ\u003e 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.","short_abstract":"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 err...","url_abs":"https://arxiv.org/abs/2507.01873","url_pdf":"https://arxiv.org/pdf/2507.01873v1","authors":"[\"Anders Aamand\",\"Justin Y. Chen\",\"Mina Dalirrooyfard\",\"Slobodan Mitrović\",\"Yuriy Nevmyvaka\",\"Sandeep Silwal\",\"Yinzhan Xu\"]","published":"2025-07-02T16:38:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Large Language Model\"]","has_code":false}