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.

Link to full version


Back to main papers page