本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。

Aug, 2020

本文提出了一种算法，用于在差分隐私（DP）的一轮（也称非交互式）本地模型中进行 k 均值聚类，该算法实现的逼近比接近于最佳非私有逼近算法，改进了以前已知的仅保证大（常数）逼近比率的算法。此外，这是第一个仅需要一轮本地 DP 模型通信的 k 均值常数逼近算法，积极地解决了 Stemmer（SODA 2020）提出的一个开放性问题。我们的算法框架非常灵活；我们通过展示在（一轮）洗牌 DP 模型中也会产生类似于最优解的逼近算法来证明这一点。

Apr, 2021

使用差分隐私的新算法定位少数点的集群，并可用于私人数据探索、聚类和去除异常值，同时大大放宽了样本和聚合技术的需求，可将非私有的分析编译为保护差分隐私的分析。

Apr, 2016

20 年前的算法经过轻微修改，适用于各种隐私模型，匹配几乎所有已知结果，改进了一些结果并扩展到新的隐私模型，即连续观测环境。

Jun, 2024

我们考虑在 $ R^d $ 中进行隐私数据集聚类的问题

Jul, 2023

该研究设计了一种新的算法，用于处理欧几里得 k - 均值问题的差分隐私，通过本地模型，可以大幅降低加性误差，同时保持乘性误差不变。

Jul, 2019

提供了最小外接球问题的数学基础背景，探讨了在 d 维欧几里德空间中确定最小半径包围给定有界集合的唯一球面。研究了与最小外接球问题相似或相关的多个问题，这些问题在科学技术的各个领域中得到了广泛应用。提出的理论框架基于几个包围和分区定理，提供了环周半径、内接半径、直径和集合宽度之间的界限和关系。这些包围和分区定理被视为该领域的基石，对其他空间和非欧几里德几何的发展和推广产生了重要影响。

Jan, 2024

通过差分隐私机制，我们研究了离散优化问题如 $k$-median 问题、顶点集覆盖、最小割、设施选址、Steiner 树和组合公开项目等，在保证客户隐私的前提下仍能获得较好的近似解，并展示了密码学定义无法做到这点的例子。

Mar, 2009

本文为研究局部隐私约束下的估计方案制定下限，推导出了私有估计和受通信限制的估计问题之间的等价性，适用于任意交互的隐私机制，并且得出了所有不同隐私保护级别的尖锐下限。作者作为对研究结果的一个重要推论，证明了有界或高斯随机向量的均值估计的最小最大均方误差按比例缩放的结论为 $d/n * d/min (ε,ε^2)$ 。

Feb, 2019

研究局部差分隐私在高斯分布参数估计中的应用，并给出了自适应的两轮解决方案和非自适应的一轮解决方案，并通过信息理论下界证明了准确性保证的紧密性。

Nov, 2018