Differentially Private Matchings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914333348331520 |
|---|---|
| author | Dinitz, Michael Li, George Z. Liu, Quanquan C. Zhou, Felix |
| author_facet | Dinitz, Michael Li, George Z. Liu, Quanquan C. Zhou, Felix |
| contents | Computing matchings in graphs is a foundational algorithmic task. Despite extensive interest in differentially private (DP) graph analysis, work on privately computing matching solutions, rather than just their size, has been sparse. The sole prior work in the standard model of pure $\varepsilon$-differential privacy, by Hsu, Huang, Roth, Roughgarden, and Wu [HHR+14, STOC'14], focused on allocations and was thus restricted to bipartite graphs. We present a comprehensive study of DP algorithms for maximum matching and b-matching in general graphs, which also yields techniques that improve upon the bipartite setting. En route to solving these matching problems, we develop a set of novel techniques with broad applicability, including a new symmetry argument for DP lower bounds, the first arboricity-based sparsifiers for node-DP, and the novel Public Vertex Subset Mechanism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Matchings Dinitz, Michael Li, George Z. Liu, Quanquan C. Zhou, Felix Data Structures and Algorithms Cryptography and Security Computing matchings in graphs is a foundational algorithmic task. Despite extensive interest in differentially private (DP) graph analysis, work on privately computing matching solutions, rather than just their size, has been sparse. The sole prior work in the standard model of pure $\varepsilon$-differential privacy, by Hsu, Huang, Roth, Roughgarden, and Wu [HHR+14, STOC'14], focused on allocations and was thus restricted to bipartite graphs. We present a comprehensive study of DP algorithms for maximum matching and b-matching in general graphs, which also yields techniques that improve upon the bipartite setting. En route to solving these matching problems, we develop a set of novel techniques with broad applicability, including a new symmetry argument for DP lower bounds, the first arboricity-based sparsifiers for node-DP, and the novel Public Vertex Subset Mechanism. |
| title | Differentially Private Matchings |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2501.00926 |