Showing cs.DSShow all
2 papers · 1 filter
cs.DS2022
A Simple Differentially Private Algorithm for Global Minimum Cut
George Z. Li
In this note, we present a simple differentially private algorithm for the global minimum cut problem using only one call to the exponential mechanism. This problem was first studi…
cs.DS2022
Differentially Private Partial Set Cover with Applications to Facility Location
George Z. Li, Dung Nguyen, Anil Vullikanti
It was observed in \citet{gupta2009differentially} that the Set Cover problem has strong impossibility results under differential privacy. In our work, we observe that these hardne…