Small Space Differentially Private Graph Algorithms in the Continual Release Model

Explore new developments in small-space differentially private graph algorithms within the continual release model in this 47-minute lecture by Quanquan Liu from the Simons Institute. Delve into groundbreaking research achieving sublinear space in the continual release model, equivalent to the sublinear space streaming model in non-DP literature. Examine the first results of their kind, covering a range of problems including densest subgraphs, k-core decomposition, maximum matching, and vertex cover. Gain insights into this innovative approach to privacy-preserving graph analysis and its implications for handling large-scale graph data with limited space constraints.

Small Space Differentially Private Graph Algorithms in the Continual Release Model