# Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries

arXiv: https://arxiv.org/abs/2408.02347 · HTML: https://mlsanity.com/paper/2408.02347/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2024.

## Built on by (most cited first, 3 of 3)

- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Total Variation Distance Estimation in Autoregressive Models](https://mlsanity.com/paper/2607.19510/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

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 tildeO(n2/varepsilon2) query complexity bound to tildeO(n/varepsilon2). 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 tildeO((log N)/varepsilon2), which for fixed varepsilon almost matches the known lower bound of Omega((log N)/loglog N). We also derive a product test for n-dimensional distributions with tildeO(n / varepsilon2) queries, and provide an Omega(√n / varepsilon2) lower bound for this property.