English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the fundamental problems of (i) uniformity testing of a discretedistribution, and (ii) closeness testing between two discrete distributionswith bounded $\ell_2$-norm. These problems have been extensively studied indistribution testing and sample-optimal estimators are known forthem~\cite{Paninski:08, CDVV14, VV14, DKN:15}.  In this work, we show that the original collision-based testers proposed forthese problems ~\cite{GRdist:00, BFR+:00} are sample-optimal, up to constantfactors. Previous analyses showed sample complexity upper bounds for thesetesters that are optimal as a function of the domain size $n$, but suboptimalby polynomial factors in the error parameter $\epsilon$. Our main contributionis a new tight analysis establishing that these collision-based testers areinformation-theoretically optimal, up to constant factors, both in thedependence on $n$ and in the dependence on $\epsilon$.

Collision-based Testers are Optimal for Uniformity and Closeness