New algorithms and lower bounds for monotonicity testing

Abstract

We consider the problem of testing whether an unknown Boolean function $f$ is monotone versus $\epsilon$-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an $\tilde{\Omega }(n^{1/5})$ lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function $f$ is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of $\Omega (\log n)$ due to Fischer et al. [FLN+02]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains $\{1,\dots ,m{\}}^n$ for all $m\ge 2$. Upper bound: We give an $\tilde{O}(n^{5/6})\text{poly}(1/\epsilon )$-query algorithm that tests whether an unknown Boolean function $f$ is monotone versus $\epsilon$-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri [CS13a], which makes $\tilde{O}(n^{7/8})\text{poly}(1/\epsilon )$ queries.

Cited by in corpus (5)

• Testing Unateness of Real-Valued Functions
• A $\tilde{O}(n)$ Non-Adaptive Tester for Unateness
• Adaptive Boolean Monotonicity Testing in Total Influence Time
• An $\tilde{O}(n)$ Queries Adaptive Tester for Unateness
• Quantum Algorithm for Monotonicity Testing on the Hypercube