Sep, 2023

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

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