New Algorithms and Lower Bounds for Monotonicity Testing
Xi Chen, Rocco A. Servedio, Li-Yang Tan · 2014
We consider the problem of testing whether an unknown Boolean function f : {- 1, 1}n→ {-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 Ω̅(n1/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}nfor all m ≥ 2. Upper bound: We present an O(n5/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(n7/8) poly(1/ε) queries.