__
Revision #1 to TR13-029 | 18th July 2013 07:25
__
#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

**Abstract:**
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.

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

More discussion on directed isoperimetry.

__
TR13-029 | 19th February 2013 08:52
__

#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

**Abstract:**
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.