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
| CREATOR | Guy Blanc, Clément L. Canonne, Erik Waingarten |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-02637