Abstract:We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for $n$-dimensional distributions that is quasi-linear in $n$, improving the previously known $\tilde{O}(n^2/\varepsilon^2)$ query complexity bound to $\tilde{O}(n/\varepsilon^2)$. We extend this result to general finite alphabets with logarithmic cost in the alphabet size.
By exploiting the specific structure of the queries that we use (which are more restrictive than general subcube queries), we obtain a cubic improvement over the best known test for distributions over $\{1,\ldots,N\}$ under the interval querying model of Canonne, Ron and Servedio (2015), attaining a query complexity of $\tilde{O}((\log N)/\varepsilon^2)$, which for fixed $\varepsilon$ almost matches the known lower bound of $\Omega((\log N)/\log\log N)$. We also derive a product test for $n$-dimensional distributions with $\tilde{O}(n / \varepsilon^2)$ queries, and provide an $\Omega(\sqrt{n} / \varepsilon^2)$ lower bound for this property.
From: Tomer Adar [view email]
[v1]
Mon, 5 Aug 2024 09:45:39 UTC (23 KB)
[v2]
Thu, 2 Jul 2026 04:59:02 UTC (23 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。