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

CREATORRóbert Busa-Fekete, Umar Syed
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13804

Browse the full library · About the Tower of Babel