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

Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu · 2025

Read Breaking the n 1.5 n^{1.5} Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition by Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01873.txt.

Description

Anders Aamand and co-authors slim down graphs while keeping secrets in this 2025 paper. A cut sparsifier is a small stand-in graph that mimics every cut of the original. Making one under differential privacy, fast, long carried a steep error floor.

Their method breaks that floor, reaching far lower additive error in polynomial time. The core is a private version of expander decomposition, a workhorse of graph algorithms. The output is a synthetic graph, safe to share, that tracks all cuts within tight bounds. The authors frame the result as a step for private network analysis.

Catalog record

CREATORAnders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, Yinzhan Xu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01873

Browse the full library · About the Tower of Babel