非自适应条件样本下等价性测试的紧致界

论文研究非自适应条件样本下的分布测试，给出等价性测试的紧致界，判定两个未知分布在全变差距离下相等或 ε-远。算法与下界证明该问题需要且仅需 $\tilde \Theta\left(\frac{\log n}{\varepsilon^2}\right)$ 次查询。结果表明非自适应条件样本下一致性、同一性与等价性测试的复杂度均为 $\tilde \Theta(\log n)$。