We give an algorithm for testing uniformity of distributions supported on hypergrids $[m]^n$, which makes $\tilde{O}(\text{poly}(m)\sqrt{n}/\epsilon^2)$ queries to a subcube conditional sampling oracle. When the side length $m$ of the hypergrid is a constant, our algorithm is nearly optimal and strengthens the algorithm of [CCK+21] which has the same query complexity but works for hypercubes $\{\pm 1\}^n$ only. A key technical contribution behind the analysis of our algorithm is a proof of a robust version of Pisier's inequality for functions over $\mathbb{Z}_m^n$ using Fourier analysis.
翻译：我们给一个子立方体有条件采样器查询$\tilde{ $[m]}(\ text{poly}(m)\sqrt{n}/\\psilon}2)$。 当超格的侧长度$m美元是一个常数时, 我们的算法几乎是最佳的, 并且加强了[CCK+21] 的算法, 它具有相同的查询复杂性, 但只对超立方体工作 $ ⁇ pm 1 ⁇ n$。 分析我们算法背后的一项关键技术贡献就是利用 Fourier 分析, 证明Pisier对超过$\mathb ⁇ m ⁇ n$的功能的不平等性。
相关内容
微信扫码咨询专知VIP会员