论文标题
在HyperGrid和$ \ widetilde {o}（n \ sqrt {d}）上的布尔函数的定向等级定理$
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester
论文作者
论文摘要
在HyperGrid上测试布尔功能的单调性的问题，$ f：[n]^d \ to \ {0,1 \} $是属性测试中的经典主题。当$ n = 2 $时，域是超立方体。对于HyperCube案例，Khot-Minzer-Safra（FOCS 2015）的突破结果给出了非自适应的单方面测试仪，使$ \ widetilde {o}（\ varepsilon^{ - 2} { - 2} \ sqrt {d} {d}）$ queries $ queries $ queries。到Polygog $ d $和$ \ varepsilon $因素，此界限与$ \widetildeΩ（\ sqrt {d}）$ - 查询非自适应下限（Chen-de-de-persedio-tan（STOC 2015），Chen-Waingarten-Xie（STOC 2017））。对于任何$ n> 2 $，最佳的非自适应复杂性都是未知的。作者的先前结果实现了一个$ \ widetilde {o}（d^{5/6}）$ - 查询上限（SODA 2020），距离$ \ sqrt {d} $ body for hypercube的$ \ sqrt {d} $很远。 在本文中，我们解决了所有常数$ n $，最多$ \ text {poly}（\ varepsilon^{ - 1} \ log d）$ factor的单调性测试的非自适应复杂性。具体来说，我们给出了一个非自适应的单方面单调测试仪，制作$ \ widetilde {o}（\ varepsilon^{ - 2} n \ sqrt {d}）$ queries。从技术角度来看，我们证明了HyperGrid $ [n]^d $的新定向等级定理。这些结果概括了著名的定向塔拉格兰不平等现象，这些不平等现象仅因超越立方体而闻名。
The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{O}(\varepsilon^{-2}\sqrt{d})$ queries. Up to polylog $d$ and $\varepsilon$ factors, this bound matches the $\widetildeΩ(\sqrt{d})$-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any $n > 2$, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a $\widetilde{O}(d^{5/6})$-query upper bound (SODA 2020), quite far from the $\sqrt{d}$ bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant $n$, up to $\text{poly}(\varepsilon^{-1}\log d)$ factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making $\widetilde{O}(\varepsilon^{-2}n\sqrt{d})$ queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid $[n]^d$. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.
