Elias, MarekKapralov, MichaelKulkarni, JanardhanLee, Yin Tat2020-08-212020-08-212020-08-212020-01-0110.1137/1.9781611975994.34https://infoscience.epfl.ch/handle/20.500.14299/171015WOS:000554408100034We propose a (epsilon, delta)-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 O (root mn/epsilon log(2) (n/delta)). This is the first construction of differentially private cut approximator that allows additive error o(m) for all m > nlog(C) n. The best known previous results gave additive O(n(3/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.asymptotic enumerationdegree sequenceapproximationtext::conference output::conference proceedings::conference paper