A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is monotone if $f(x) \geq f(y)$ whenever $x > y$, that is, all coordinates of $x$ dominate those of $y$. $f$ is $\epsilon$-far from monotone if the function needs to be changed in at least $\epsilon$ fraction of the domain points to make it monotone. We are interested in the problem of distinguishing monotone functions from those that are $\epsilon$-far, given only query access to the function, making as few queries to the function as possible. There is a relatively easy tester making $O(n/\epsilon)$-queries from 2000. In this talk, I'll show a slightly more sophisticated tester which makes $o(n)$ queries (to be precise, it makes $O(n^{5/6}/\epsilon^{10/3})$ queries).
One of the main ingredients will be an isoperimetry result on the *directed* hypercube, where the edges of the hypercube are directed from $y$ to $x$ if $x > y$. In particular, we show that the support set (the $x$'s s.t. $f(x)=1$) of a $\epsilon$-far from monotone function, either have a large directed edge expansion, or a large directed vertex expansion (joint work with C. Seshadhri).
