We study distribution testing in the standard access model and the
conditional access model when the memory available to the testing algorithm is
bounded. In both scenarios, the samples appear in an online fashion and the
goal is to test the properties of distribution using an optimal number of
samples subject to a memory constraint on how many samples can be stored at a
given time. First, we provide a trade-off between the sample complexity and the
space complexity for testing identity when the samples are drawn according to
the conditional access oracle. We then show that we can learn a succinct
representation of a monotone distribution efficiently with a memory constraint
on the number of samples that are stored that is almost optimal. We also show
that the algorithm for monotone distributions can be extended to a larger class
of decomposable distributions.

在标准访问模型和条件访问模型中，当测试算法的内存受到限制时，我们研究分布测试。我们提供了一个样本复杂性和空间复杂性之间的权衡，用于在根据条件访问预言进行抽样时测试身份。我们还展示了我们可以有效地学习具有几乎最优的样本存储限制的单调分布的简洁表示。此外，我们还展示了单调分布的算法可以扩展到更大的可分解分布类。

在数据流模型中测试分布属性

Testing properties of distributions in the streaming model

A $k$-modal probability distribution over the discrete domain $\{1,...,n\}$
is one whose histogram has at most $k$ "peaks" and "valleys." Such
distributions are natural generalizations of monotone ($k=0$) and unimodal
($k=1$) probability distributions, which have been intensively studied in
probability theory and statistics.
In this paper we consider the problem of \emph{learning} (i.e., performing
density estimation of) an unknown $k$-modal distribution with respect to the
$L_1$ distance. The learning algorithm is given access to independent samples
drawn from an unknown $k$-modal distribution $p$, and it must output a
hypothesis distribution $\widehat{p}$ such that with high probability the total
variation distance between $p$ and $\widehat{p}$ is at most $\epsilon.$ Our
main goal is to obtain \emph{computationally efficient} algorithms for this
problem that use (close to) an information-theoretically optimal number of
samples.
We give an efficient algorithm for this problem that runs in time
$\mathrm{poly}(k,\log(n),1/\epsilon)$. For $k \leq \tilde{O}(\log n)$, the
number of samples used by our algorithm is very close (within an
$\tilde{O}(\log(1/\epsilon))$ factor) to being information-theoretically
optimal. Prior to this work computationally efficient algorithms were known
only for the cases $k=0,1$ \cite{Birge:87b,Birge:97}.
A novel feature of our approach is that our learning algorithm crucially uses
a new algorithm for \emph{property testing of probability distributions} as a
key subroutine. The learning algorithm uses the property tester to efficiently
decompose the $k$-modal distribution into $k$ (near-)monotone distributions,
which are easier to learn.

本文针对 $k$- 模态分布，提出了一种密度估计的学习算法，利用性质测试算法实现分布分解，从而实现对不同峰值与谷值情况的分布的有效估计。