我们开启了对 $\{\pm1\}^n$ 上的 单调分布 的研究，这是一种自然的单调布尔函数的类比，重点关注两个基本测试问题，这些问题与单调分布的成熟研究问题高度相关：
-
单调分布的均匀性测试：我们证明了 $\widetilde{\Theta}(n^{3/2})$ 的样本量是充分且必要的，而对于单调分布的类似问题，样本复杂度为 $\widetilde{\Theta}(n)$（Rubinfeld 和 Servedio，STOC 2005；Adamaszek, Czumaj, 和 Sohler，SODA 2010）。
-
任意分布的单调性测试：我们提供了一个测试器，在子立方体条件模型中使用 $\widetilde{O}(n^{3/2})$ 的条件样本。另一方面，任何以类似方式从 $O(1)$ 维子立方体中提取条件样本的测试器，其复杂度必须为 $\widetilde{\Omega}(n^{2/3})$。在同一模型中，单调性测试的复杂度最近被证明为 $\widetilde{\Theta}(n)$（Chakrabarty 等，STOC 2025）。
我们的算法在这两个问题上显著优于简单减少到单调情况的方法，后者会导致样本复杂度达到 $\Omega(n^2)$。我们的均匀性测试器依赖于一个子例程，该子例程“弱地”学习单调分布的隐藏方向，以及一个新的相关性界限。这两种工具在研究 $\{\pm1\}^n$ 上的单调性和单调性方面可能具有独立的研究价值。
博主点评： 本文通过引入单调分布的测试，展示了单调性与均匀性之间的深刻联系，尤其是在样本复杂度方面的显著差异，值得进一步探索其在实际应用中的潜力。