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 ... more >>>

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 ... more >>>

Testing monotonicity of Boolean functions over the hypergrid, f:[n]^d \to \{0,1\}, is a classic problem in property testing. When the range is real-valued, there are \Theta(d\log n)-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of n: There are testers ... more >>>