Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to be modified at $\eps$-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes $\widetilde{O}(n^{7/8}\eps^{-3/2})$ queries to the oracle.

Fixed a bug in previous version. The running time is now $n^{7/8}$ instead of $n^{5/6}$.

More discussion on directed isoperimetry.

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to be modified at $\eps$-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes $\widetilde{O}(n^{5/6}\eps^{-5/3})$ queries to the oracle.