Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $n$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$. This complexity is independent of $n$, but has a suboptimal dependence on $d$. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$ and $\widetilde{O}(\varepsilon^{-2} n\sqrt{d})$-query testers, respectively. These testers have an almost optimal dependence on $d$, but a suboptimal polynomial dependence on $n$. In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity $O(\varepsilon^{-2} d^{1/2 + o(1)})$, independent of $n$. Up to the $d^{o(1)}$-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $n$ yields a non-adaptive, one-sided $O(\varepsilon^{-2} d^{1/2 + o(1)})$-query monotonicity tester for Boolean functions $f:\mathbb{R}^d \to \{0,1\}$ associated with an arbitrary product measure.
翻译：一个基于$d$维超立方体的布尔函数的$d^{1/2+o(1)}$单调性测试器
摘要：
布尔函数在超立方体（$f:[n]^d \to \{0,1\}$）上的单调性测试是一个经典的属性测试话题。确定这个问题的非自适应复杂度是一个重要的开放问题。对于任意的$n$，[Black-Chakrabarty-Seshadhri，SODA 2020]描绘了一个带有查询复杂度$\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$的测试器。这个复杂度不依赖于$n$，但具有次优的对$d$的依赖性。最近，[Braverman-Khot-Kindler-Minzer，ITCS 2023]和[Black-Chakrabarty-Seshadhri，STOC 2023]分别描述了带有$\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$和$\widetilde{O}(\varepsilon^{-2} n\sqrt{d})$查询测试器。这些测试器在$d$上有一个几乎最优的依赖关系，但在$n$上具有次优的多项式依赖性。在本文中，我们描述了一个非自适应，单侧单调性测试器，其查询复杂度为$O(\varepsilon^{-2} d^{1/2 + o(1)})$，并且独立于$n$。在$d^{o(1)}$因子的范围内，我们的结果解决了超立方体上布尔函数单调性测试的非自适应复杂度问题。$n$的独立性产生了一个非自适应的、单侧的，基于任意乘积测度的布尔函数$f:\mathbb{R}^d \to \{0,1\}$的$O(\varepsilon^{-2} d^{1/2 + o(1)})$查询单调性测试器。
相关内容
微信扫码咨询专知VIP会员