We study the question of testing structured properties (classes) of discrete
distributions. Specifically, given sample access to an arbitrary distribution
$D$ over $[n]$ and a property $\mathcal{P}$, the goal is to distinguish between
$D\in\mathcal{P}$ and $\ell_1(D,\mathcal{P})>\varepsilon$. We develop a general
algorithm for this question, which applies to a large range of
"shape-constrained" properties, including monotone, log-concave, $t$-modal,
piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all
cases considered, our algorithm has near-optimal sample complexity with regard
to the domain size and is computationally efficient. For most of these classes,
we provide the first non-trivial tester in the literature. In addition, we also
describe a generic method to prove lower bounds for this problem, and use it to
show our upper bounds are nearly tight. Finally, we extend some of our
techniques to tolerant testing, deriving nearly-tight upper and lower bounds
for the corresponding questions.

本文主要研究了离散分布的结构性质（类），提出了一个通用的算法，可以测试各种形状约束的属性，包括单调、对数凹、t - 模态、分段多项式和泊松二项式分布。此外，对于所有考虑的情况，算法在领域大小方面具有近乎最优的样本复杂度，并且计算效率高。