2 papers
cs.CR2024
Almost linear time differentially private release of synthetic graphs
Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou
In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an -score function defined over an exponentially large non-co…
cs.DS2023
Optimal Bounds on Private Graph Approximation
Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou
We propose an efficient -differentially private algorithm, that given a simple {\em weighted} -vertex, -edge graph with a \emph{maximum unweighted} degree $Δ(G) \leq n…