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…