4 papers · 1 filter
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li +3
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k…
Practical and Accurate Local Edge Differentially Private Graph Algorithms
Pranay Mundra, Charalampos Papamanthou, Julian Shun +1
The rise of massive networks across diverse domains necessitates sophisticated graph analytics, often involving sensitive data and raising privacy concerns. This paper addresses th…
Near-Optimal Differentially Private k-Core Decomposition
Laxman Dhulipala, George Z. Li, Quanquan C. Liu
Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the -core decomposition problem under differential privacy via a connection between low round/depth distri…
Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs
Pattara Sukprasert, Quanquan C. Liu, Laxman Dhulipala +1
The densest subgraph problem has received significant attention, both in theory and in practice, due to its applications in problems such as community detection, social network ana…