4 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…