Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
X. Chen and R. Servedio and L.-Y. Tan and Erik Waingarten and Jinyu Xie.
21st International Workshop on Randomness and Computation (RANDOM), 2017, pp. 38:1--38:21.

Abstract:

We give a $\poly(\log n, 1/\eps)$-query adaptive algorithm for testing whether an unknown Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, which is promised to be a halfspace, is monotone versus $\eps$-far from monotone. Since non-adaptive algorithms are known to require almost $\Omega(n^{1/2})$ queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.