Boolean Monotonicity Testing over the Hypercube and Directed Isoperimetric Questions

The problem of monotonicity testing on the hypercube is as follows. Given a Boolean function f over the d-dimensional hypercube, we wish to design an algorithm to distinguish between f being monotone and f being far from monotone. Old results proved the existence of O(d) algorithms. Recent advances have shown the existence of o(d) algorithms.

But rather than the algorithms themselves, these results uncover a surprising phenomenon. Classic isoperimetric results over the hypercube by Margulis and Talagrand can be converted (with significant effort) into ""directed"" isoperimetric analogues. The role of the variance of f is replaced by the distance to monotonicity.

We will give a survey of these results, and talk about some new directed isoperimetric results for hypergrids. These new results attempt to understand the core reason why such isoperimetric results hold. These results, in turn, lead to new monotonicity testers of the richer class of hypergrid domains.