Small Space Differentially Private Graph Algorithms in the Continual Release Model

This talk will feature new work on small-space differentially private graph algorithms in the continual release model. We present the first results that achieve sublinear space in the continual release model which is the DP model equivalent to the sublinear space streaming model commonly known in non-DP literature. Our results cover a variety of problems including densest subgraphs, k-core decomposition, maximum matching, and vertex cover.