arXiv:2504.13804v1 交叉类型:公共公告 摘要: 我们提出了估计和测试碰撞概率的新算法，碰撞概率是广泛应用于许多科学领域的离散分布扩展性的一个基本度量。我们描述了一个满足$(\alpha, \beta)$-局部差分隐私的算法，并且使用$\tilde{O}\left(\frac{\log(1/\beta)}{\alpha^2 \epsilon^2}\right)$样本来估计碰撞概率，其误差不超过$\epsilon$，这比之前的成果改进了$\frac{1}{\alpha^2}$个数量级。我们还提出了一种用于碰撞概率的顺序测试算法，在未知$\epsilon$的情况下，仅使用$\tilde{O}(\frac{1}{\epsilon^2})$样本，就可以区分开差距为$\epsilon$的碰撞概率值。我们的算法几乎具有最优的样本复杂度，而在实验中我们展示了它们所需要的样本数量远远少于以前的方法。