Uniformity Testing over Hypergrids with Subcube Conditioning

Xi Chen, Cassandra Marcussen

We give an algorithm for testing uniformity of distributions supported on hypergrids $[m_1]\times \cdots \times [m_n]$, which makes $\smash{\widetilde{O}(\text{poly}(m)\sqrt{n}/ε^…