## On Monotonicity Testing and Boolean Isoperimetric type Theorems

by Subhash Khot, Dor Minzer, and Muli Safra.

Well, this finally nails the question of determining the query complexity of testing Monotonicity of Boolean functions. Specifically, they showed that a suitbale pair tester rejects Boolean functions that are $\eps$-far from monotone with probability at least $\eps^2/\sqrt n$.
We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from being monotone with constant probability.