Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling

Felix Zhou

We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms, with a focus on the densest subgraph problem (DSG) in the insertion-only…