New algorithms and lower bounds for monotonicity testing

We consider the problem of testing whether an unknown Boolean function $f$ is monotone versus $ε$-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Ω(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 $Ω(\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,\ldots,m\}^n$ for all $m\ge 2$. Upper bound: We give an $\tilde{O}(n^{5/6})\text{poly}(1/ε)$-query algorithm that tests whether an unknown Boolean function $f$ is monotone versus $ε$-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/ε)$ queries.

No reviews yet.

No comments yet.