On Computing Pairwise Statistics with Local Differential Privacy
<|reference_start|>On Computing Pairwise Statistics with Local Differential Privacy: We study the problem of computing pairwise statistics, i.e., ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $\tau$ 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.<|reference_end|>
@article{ghazi2024on,
    title={On Computing Pairwise Statistics with Local Differential Privacy},
    author={Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi and Adam
  Sealfon},
    journal={arXiv preprint arXiv:2406.16305},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.16305},
    primaryClass={cs.DS cs.CR}
}