1 citations · 1 across the 7 of their papers we have counts for
9 papers
Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error
Marek Eliáš, Gautam Kamath, Janardhan Kulkarni +7
We give a polynomial-time -edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted…
Pure Differentially Private Query Release via Laplace Input Smoothing
Zongrui Zou
We study the offline release of a public family of statistical queries on a database of records from a public universe of size , under pure -differential pr…
Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers
Chenglin Fan, Jingcheng Liu, Pan Peng +2
We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additi…
The Price of Privacy For Approximating Max-CSP
Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi +3
We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Infor…
A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
Michael Dinitz, Chenglin Fan, Jingcheng Liu +2
We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected…
Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
Rishi Chandra, Michael Dinitz, Chenglin Fan +1
In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum -cut. We introduce edge-d…
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…
Optimality of Matrix Mechanism on -metric
Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou
In this paper, we introduce the -error metric (for ) when answering linear queries under the constraint of differential privacy. We characterize such an error u…
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…