Boolean Monotonicity Testing via an Isoperimetry Result on the Directed Hypercube

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 \eps-far from monotone if the function needs to be changed in at least \eps fraction of the domain points to make it monotone. We are interested in the problem of distinguishing monotone functions from those that are \eps-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/\eps)-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}/\eps^{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 \eps-far from monotone function, either have a large directed edge expansion, or a large directed vertex expansion (joint work with C. Seshadhri).