Instance-Optimal Uniformity Testing and Tracking

Guy Blanc, Clément L. Canonne, Erik Waingarten · 2025

Read Instance-Optimal Uniformity Testing and Tracking by Guy Blanc, Clément L. Canonne, Erik Waingarten (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-2508-02637.txt.

Description

Guy Blanc, Clément Canonne, and Erik Waingarten revisit a classic problem in computer science: testing whether samples come from a uniform distribution. The standard task demands a preset gap, yet that setup can waste samples and miss real-world cases. Deviations do not announce their shape in advance.

The authors define a new task, uniformity tracking, which asks an algorithm to catch any drift from uniform with as few samples as it can. The algorithm must rival the best method that knew the true pattern beforehand. Their tracker stays within a small factor of that ideal. The proof leans on new results about Poisson mixtures, which they flag as useful beyond this problem.

Catalog record

CREATORGuy Blanc, Clément L. Canonne, Erik Waingarten
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-02637

Browse the full library · About the Tower of Babel