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

Distribution testing can be described as follows: $q$ samples are being drawnfrom some unknown distribution $P$ over a known domain $[n]$. After thesampling process, a decision must be made about whether $P$ holds someproperty, or is far from it. The most studied problem in the field is arguablyuniformity testing, where one needs to distinguish the case that $P$ is uniformover $[n]$ from the case that $P$ is $\epsilon$-far from being uniform (in$\ell_1$). In the classic model, it is known that$\Theta\left(\sqrt{n}/\epsilon^2\right)$ samples are necessary and sufficientfor this task. This problem was recently considered in various restrictedmodels that pose, for example, communication or memory constraints. In morethan one occasion, the known optimal solution boils down to counting collisionsamong the drawn samples (each two samples that have the same value add one tothe count), an idea that dates back to the first uniformity tester, and wascoined the name "collision-based tester".  In this paper, we introduce the notion of comparison graphs and use it toformally define a generalized collision-based tester. Roughly speaking, theedges of the graph indicate the tester which pairs of samples should becompared (that is, the original tester is induced by a clique, where all pairsare being compared). We prove a structural theorem that gives a sufficientcondition for a comparison graph to induce a good uniformity tester. As anapplication, we develop a generic method to test uniformity, and devisenearly-optimal uniformity testers under various computational constraints. Weimprove and simplify a few known results, and introduce a new constrained modelin which the method also produces an efficient tester.  The idea behind our method is to translate computational constraints of acertain model to ones on the comparison graph, which paves the way to finding agood graph.

Comparison Graphs: a Unified Method for Uniformity Testing