UC San Diego

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 e-far from p, in L1 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.