A Simple Differentially Private Algorithm for Global Minimum Cut

Autor:	Li, George Z.
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Cryptography and Security
Druh dokumentu:	Working Paper
Popis:	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 studied by Gupta et al. [2010], and they gave a differentially private algorithm with near-optimal utility guarantees. We improve upon their work in many aspects: our algorithm is simpler, more natural, and more efficient than the one given in Gupta et al. [2010], and furthermore provides slightly better privacy and utility guarantees. Comment: There is an error in the privacy argument. The algorithm only outputs t such that the minimum s-t cut (S_t,V-S_t) gives an O(log n/eps) approximation. There is currently no way to privately compute min s-t cut, so this doesn't do anything
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2208.09365 Zobrazit plný text záznamu View this record from Arxiv