1 citations · 1 across the 7 of their papers we have counts for
7 papers
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…