New Algorithms and Lower Bounds for Monotonicity Testing

We consider the problem of testing whether an unknown Boolean function f : {- 1, 1}ⁿ → {-1, 1} 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 Ω̅(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. [1]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains {1,···, m}ⁿ for all m ≥ 2. Upper bound: We present an O(n^5/6) 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[2], which makes O(n^7/8) poly(1/ε) queries.