  Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the
$k$-core decomposition problem under differential privacy via a connection
between low round/depth distributed/parallel graph algorithms and private
algorithms with small error bounds. They showed that one can output
differentially private approximate $k$-core numbers, while only incurring a
multiplicative error of $(2 +\eta)$ (for any constant $\eta >0$) and additive
error of $\poly(\log(n))/\eps$. In this paper, we revisit this problem. Our
main result is an $\eps$-edge differentially private algorithm for $k$-core
decomposition which outputs the core numbers with no multiplicative error and
$O(\text{log}(n)/\eps)$ additive error. This improves upon previous work by a
factor of 2 in the multiplicative error, while giving near-optimal additive
error. Our result relies on a novel generalized form of the sparse vector
technique, which is especially well-suited for threshold-based graph
algorithms; thus, we further strengthen the connection between
distributed/parallel graph algorithms and differentially private algorithms.
