Near-optimal algorithms for private estimation and sequential testing of collision probability
Róbert Busa-Fekete, Umar Syed · 2025
Read Near-optimal algorithms for private estimation and sequential testing of collision probability by Róbert Busa-Fekete, Umar Syed (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13804.txt.
Description
Róbert Busa-Fekete and Umar Syed give near-optimal private algorithms for estimating how spread out a distribution is, in a 2025 paper. Collision probability measures the chance that two draws match. It is a basic gauge of concentration used across science. Privacy rules complicate its estimation from sensitive data.
One algorithm estimates the value under local differential privacy. Its sample needs improve on prior work by a wide factor. A second algorithm tests between two candidate values in sequence. It stops as soon as the evidence is clear, even without knowing the gap in advance. Experiments confirm the theory's practical edge. Data custodians gain sharper tools for private analytics.
Catalog record
| CREATOR | Róbert Busa-Fekete, Umar Syed |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-13804