我们研究了由 Bhattacharyya 和 Chakraborty(2017)提出的子立方体条件模型中的属性测试。我们获得了第一个针对 $n$ 维分布的等价性测试,其查询复杂度为准线性的 $\tilde{O}(n/\boldsymbol{\varepsilon}^2)$,这是对之前已知的 $\tilde{O}(n^2/\boldsymbol{\varepsilon}^2)$ 查询复杂度界限的重要改进。
我们将此结果扩展到具有对数成本的一般有限字母表中。通过利用我们使用的查询的特定结构(这些查询比一般的子立方体查询更为严格),我们在 Canonne、Ron 和 Servedio(2015)提出的区间查询模型下,获得了对 $N$ 的分布的最佳已知测试的立方体改进,达到了查询复杂度 $\tilde{O}((\log N)/\boldsymbol{\varepsilon}^2)$,对于固定的 $\boldsymbol{\varepsilon}$,几乎达到了已知的下界 $\boldsymbol{\Omega}((\log N)/\log\log N)$。
此外,我们还推导出针对 $n$ 维分布的乘积测试,其查询复杂度为 $\tilde{O}(n / \boldsymbol{\varepsilon}^2)$,并为此属性提供了 $\boldsymbol{\Omega}(\sqrt{n} / \boldsymbol{\varepsilon}^2)$ 的下界。