Recent work by Dhulipala, Liu, Raskhodnikova, Shi, Shun, and Yu [DLRSSY, FOCS 2022] initiated the study of the relationship between parallel and distributed graph algorithms and differentially private graph algorithms, giving the best known algorithms for differentially private densest subgraph and k-core decomposition in the central and local models. In this paper we continue on this line of work, investigating how ideas from recent work on sublinear graph algorithms can be used in designing better differentially private graph algorithms. We give an ε-edge differentially private algorithm for k-core decomposition which outputs the core numbers (for any constant η>0) with (1+η)-multiplicative and O(log(n)/ε) additive error. This improves upon the best known guarantees for differentially private k-core decomposition by a factor of 2 in the multiplicative error, while giving near-optimal additive error.
George is an undergraduate student at the University of Maryland, advised by Aravind Srinivasan. He is interested broadly in theoretical computer science, and has primarily worked on randomized algorithms and differential privacy. He is a 2022 Goldwater Scholar and much more to come.