Fine-Grained Privacy Guarantees for Coverage Problems
CoRR(2024)
摘要
We introduce a new notion of neighboring databases for coverage problems such
as Max Cover and Set Cover under differential privacy. In contrast to the
standard privacy notion for these problems, which is analogous to node-privacy
in graphs, our new definition gives a more fine-grained privacy guarantee,
which is analogous to edge-privacy. We illustrate several scenarios of Set
Cover and Max Cover where our privacy notion is desired one for the
application.
Our main result is an ϵ-edge differentially private algorithm for
Max Cover which obtains an (1-1/e-η,Õ(k/ϵ))-approximation
with high probability. Furthermore, we show that this result is nearly tight:
we give a lower bound show that an additive error of Ω(k/ϵ) is
necessary under edge-differential privacy. Via group privacy properties, this
implies a new algorithm for ϵ-node differentially private Max Cover
which obtains an (1-1/e-η,Õ(fk/ϵ))-approximation, where f
is the maximum degree of an element in the set system. When f≪ k, this
improves over the best known algorithm for Max Cover under pure (node)
differential privacy, which obtains an
(1-1/e,Õ(k^2/ϵ))-approximation.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要