# On Computing Pairwise Statistics with Local Differential Privacy

arXiv: https://arxiv.org/abs/2406.16305 · HTML: https://mlsanity.com/paper/2406.16305/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2024.

## Built on by (most cited first, 3 of 3)

- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [On Differentially Private U Statistics](https://mlsanity.com/paper/2407.04945/) (2024)
- [Accurate, private, secure, federated U-statistics with higher degree](https://mlsanity.com/paper/2603.01986/) (2026)

## Abstract (arXiv)

We study the problem of computing pairwise statistics, i.e., ones of the form binomn2-1 sumi ne j f(xi, xj), where xi denotes the input to the ith user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's τ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.