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

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.