2023/12/12 by Dhulipala, Laxman, Li, George Z., Liu, Quanquan C. · 3 citations
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.2312.07706
Recent work by Dhulipala et al. \citeDLRSSY22 initiated the study of the k-core decomposition problem under differential privacy via a connection between low round/depth distributed/parallel graph algorithms and private algorithms with small error bounds. They showed that one can output differentially private approximate k-core numbers, while only incurring a multiplicative error of (2 +η) (for any constant η>0) and additive error of \poly(log(n))/\eps. In this paper, we revisit this problem. Our main result is an \eps-edge differentially private algorithm for k-core decomposition which outputs the core numbers with no multiplicative error and O(log(n)/\eps) additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error. Our result relies on a novel generalized form of the sparse vector technique, which is especially well-suited for threshold-based graph algorithms; thus, we further strengthen the connection between distributed/parallel graph algorithms and differentially private algorithms.