本文研究了差分隐私机制在 $d$ 个非适应性线性查询的噪音复杂度，使用几何参数给出了噪音复杂度的上下界，并根据凸几何学中的超平面猜想证明了任意线性查询的结果，提高了先前的结果，揭示了差分隐私概念与近似差分隐私概念之间的分离。

Jul, 2009

该研究通过指定参数 delta 来构建一个全新的下界，从而优化（epsilon，delta）差分隐私算法在高维数据库上精确回答统计查询的样本复杂度。除了新的下界之外，该研究还提出了纯粹和近似的差分隐私算法，用于回答任意统计查询，并通过对比标准拉普拉斯和高斯机制在最坏情况下精度保证方面的样本复杂度，改善了对该问题的解决方法。

Jan, 2015

提供严格多项式时间的离散算法，用于近似分类数据集的直方图，同时保留与拉普拉斯机制相同的（纯）差分隐私保证，并基于受限离散计算模型，避免了基于实际算术的不同隐私算法攻击实现的可能性。

Sep, 2017

研究使用局部差分隐私约束下的敏感数据集来估计一组关于一些未知分布的 $d$ 个线性查询的问题，提出了离线和自适应问题的新算法。

Oct, 2018

该研究提供了基于不同隐私数据发布的样本复杂度下限的新方法，并给出了一些新的评估策略。

Nov, 2013

本文提出了第一个用于回答批量线性查询的实用差分隐私技术，即低秩机制 (LRM)，它适用于确切和近似差分隐私定义，并提供对 LRM 的实用性保证，同时提供如何根据用户的实用预期设置隐私参数的指导。与差分隐私下的最新查询处理解决方案相比，这种方法在真实数据上的大规模实验中表现出了更高的准确性。

Feb, 2015

通过指纹技术和贝叶斯方法，我们改进了高维度隐私估计的下界。我们提出了计算高斯协方差和重尾分布均值的样本数量下界，并与先前工作的结论进行了比较。

Oct, 2023

探讨平衡标准误差和隐私保护之间的关系，提出了最小化极限风险下的差分隐私约束的算法，包括隐私迭代硬阈值追踪，以及在实际数据集中表现出的数值表现。

Feb, 2019

本文提出了单一实值查询函数的最优 ε- 差分隐私机制，其噪声概率分布类具有楼梯形状、对称性、单调递减和几何衰减，可以被视为均匀概率分布的几何混合，并将此机制自然地推广到了离散查询输出环境和更抽象的环境中。通过将最优性能与拉普拉斯机制的性能进行比较，我们得出结论，当 ε 趋近于 0 时，拉普拉斯机制是渐近最优的；而在 ε 趋近于 +∞时，最小噪声振幅和最小噪声功率分别为 Θ(Δe^-ε/2) 和 Θ(Δ^2 e^-2ε/3)，而拉普拉斯机制的噪声振幅和功率期望分别为 Δ/ε 和 2Δ^2/ε^2，在低隐私保护级别下获得更明显的收益。

Dec, 2012

论文介绍了在差分隐私约束下回答线性查询时的 $\ell_p^p$ 误差度量（$p \geq 2$）。我们通过 $(\epsilon,\delta)$- 差分隐私对此误差进行了特征化。同时，我们给出了回答前缀和查询的紧密界限，并将其泛化到所有常数 $p$ 的情况下。

Jun, 2024