Reposted by Jalaj Upadhyay
JAX-Privacy: A library for differentially private machine learning
Ryan McKenna, Galen Andrew, Borja Balle, Vadym Doroshenko, Arun Ganesh, Weiwei Kong, Alex Kurakin, Brendan McMahan, Mikhail Pravilov
arxiv.org/abs/2602.17861
![Breaking the $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
http://arxiv.org/abs/2507.01873
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+\gamma$ multiplicative error for
any $\gamma > 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+\gamma$ multiplicative error
[Eli{\'a}{\v{s}}, 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,\delta)$-DP polynomial time algorithm that, given a
non-negative weighted graph, outputs a private synthetic graph approximating
all cuts with multiplicative error $1+\gamma$ and additive error $n^{1.25 +
o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$).
At the heart of our approach lies a private algorithm for expander
decomposition, a popular and powerful technique in (non-private) graph
algorithms.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:bvdt4psvley2chbqednjkkw2/bafkreihscv3gm3gw5dazigc5yl4n4atklmta52vlgp5kf54ph7d7cg4b4m)
![Differentially Private Matchings
Michael Dinitz, George Z. Li, Quanquan C. Liu, Felix Zhou
http://arxiv.org/abs/2501.00926
Computing matchings in general graphs plays a central role in graph
algorithms. However, despite the recent interest in differentially private
graph algorithms, there has been limited work on private matchings. Moreover,
almost all existing work focuses on estimating the size of the maximum
matching, whereas in many applications, the matching itself is the object of
interest. There is currently only a single work on private algorithms for
computing matching solutions by [HHRRW STOC'14]. Moreover, their work focuses
on allocation problems and hence is limited to bipartite graphs.
Motivated by the importance of computing matchings in sensitive graph data,
we initiate the study of differentially private algorithms for computing
maximal and maximum matchings in general graphs. We provide a number of
algorithms and lower bounds for this problem in different models and settings.
We first prove a lower bound showing that computing explicit solutions
necessarily incurs large error, even if we try to obtain privacy by allowing
ourselves to output non-edges. We then consider implicit solutions, where at
the end of the computation there is an ($\varepsilon$-differentially private)
billboard and each node can determine its matched edge(s) based on what is
written on this publicly visible billboard. For this solution concept, we
provide tight upper and lower (bicriteria) bounds, where the degree bound is
violated by a logarithmic factor (which we show is necessary). We further show
that our algorithm can be made distributed in the local edge DP (LEDP) model,
and can even be done in a logarithmic number of rounds if we further relax the
degree bounds by logarithmic factors. Our edge-DP matching algorithms give rise
to new matching algorithms in the node-DP setting by combining our edge-DP
algorithms with a novel use of arboricity sparsifiers. [...]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:bvdt4psvley2chbqednjkkw2/bafkreibqicstpwidnxdhsnhzm65cbmnyftf3ttdeps4lpevj2z6okjbcfi)
