Differentially Private Multiway and $k$-Cut

本文探讨了在图割问题中如何保证差分隐私，特别是关注最小$k$割和多元割问题。我们提出了一种边界差分隐私算法，可实现这些问题的几乎最优性能。对于多元割问题，我们首先提供了一个具有乘法逼近比的隐私算法，与最先进的非隐私算法相匹配。然后，我们提出了一个紧密的信息论下界，证明我们在加权图上的算法在常数$k$的情况下是近乎最优的。对于最小$k$割问题，我们的算法利用了关于近似$k$割数量的已知界限，从而得到了一个具有最优加法误差$O(k\log n)$的隐私算法，固定隐私参数。我们还建立了一个信息论下界，与此加法误差相匹配。此外，我们还提供了一个高效的$k$-割隐私算法，即使对于非常数$k$，也包括一个多项式时间的2-逼近算法，具有$\widetilde{O}(k^{1.5})$的加法误差。

本篇论文主要解决图割中的差分隐私问题，特别是最小k割和多向割问题。论文介绍了能够在这些问题中实现几乎最优性能的边差分隐私算法。

该论文提出了一种边差分隐私算法，用于实现最小k割和多向割问题，其中多向割问题的乘法逼近比例与最优非隐私算法相匹配。对于最小k割问题，算法利用已知的近似k割数量上限，得出了一个隐私算法，其固定隐私参数的最优加性误差为O（k log n）。此外，还提出了一种用于非常数k的高效隐私算法，包括具有O（k ^ 1.5）加性误差的多项式时间2逼近。

该论文的亮点是提出了边差分隐私算法，实现了最小k割和多向割问题的几乎最优性能。对于多向割问题，乘法逼近比例与最优非隐私算法相匹配。对于最小k割问题，算法利用已知的近似k割数量上限，得出了一个隐私算法，其固定隐私参数的最优加性误差为O（k log n），并且还提出了一种用于非常数k的高效隐私算法，包括具有O（k ^ 1.5）加性误差的多项式时间2逼近。

最近的相关研究包括在图割中使用差分隐私的其他方法，以及在差分隐私领域中的其他应用。例如，论文提到了使用差分隐私的聚类算法和机器学习算法。