Near-optimal algorithms for private estimation and sequential testing of collision probability

Robert Busa-Fekete, Umar Syed

We present new algorithms for estimating and testing \emph{collision probability}, a fundamental measure of the spread of a discrete distribution that is widely used in many scient…