%0 Journal Article %1 diakonikolas2014testing %A Diakonikolas, Ilias %A Kane, Daniel M. %A Nikishkin, Vladimir %D 2014 %K stats %T Testing Identity of Structured Distributions %U http://arxiv.org/abs/1410.2266 %X We study the question of identity testing for structured distributions. More precisely, given samples from a structured distribution $q$ over $n$ and an explicit distribution $p$ over $n$, we wish to distinguish whether $q=p$ versus $q$ is at least $\epsilon$-far from $p$, in $L_1$ distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including $t$-flat distributions, $t$-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.

@article{diakonikolas2014testing, abstract = {We study the question of identity testing for structured distributions. More precisely, given samples from a {\em structured} distribution $q$ over $[n]$ and an explicit distribution $p$ over $[n]$, we wish to distinguish whether $q=p$ versus $q$ is at least $\epsilon$-far from $p$, in $L_1$ distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including $t$-flat distributions, $t$-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.}, added-at = {2020-02-26T13:46:43.000+0100}, author = {Diakonikolas, Ilias and Kane, Daniel M. and Nikishkin, Vladimir}, biburl = {https://www.bibsonomy.org/bibtex/270c0179f4a1443ee9147f631300f6497/kirk86}, description = {[1410.2266] Testing Identity of Structured Distributions}, interhash = {cdb5c2cd8931700c698c494367953434}, intrahash = {70c0179f4a1443ee9147f631300f6497}, keywords = {stats}, note = {cite arxiv:1410.2266Comment: 21 pages, to appear in SODA'15}, timestamp = {2020-02-26T13:46:43.000+0100}, title = {Testing Identity of Structured Distributions}, url = {http://arxiv.org/abs/1410.2266}, year = 2014 }