@inproceedings{eli2020differentially,
author = {Eliáš, Marek and Kapralov, Michael and Kulkarni, Janardhan (Jana) and Lee, Yin Tat},
title = {Differentially private release of synthetic graphs},
organization = {Microsoft Research},
booktitle = {2020 Symposium on Discrete Algorithms},
year = {2020},
month = {January},
abstract = {We propose a (ϵ, Δ)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G' approximating all cuts of the input graph up to an additive error of [MATH HERE]. This is the first construction of differentially private cut approximator that allows additive error o(m) for all m > nlogC n. The best known previous results gave additive O(n3/2) error and hence only retained information about the cut structure on very dense graphs. Thus, we are making a notable progress on a promiment problem in differential privacy. We also present lower bounds showing that our utility/privacy tradeoff is essentially the best possible if one seeks to get purely additive cut approximations.},
url = {http://approjects.co.za/?big=en-us/research/publication/differentially-private-release-of-synthetic-graphs/},
pages = {560-578},
}