On Monotonicity Testing and Boolean Isoperimetric type Theorems

by Subhash Khot, Dor Minzer, and Muli Safra.

Oded's comments

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$.

The introduction links a key issue that arises in the analysis of the analysis of natural monotonicity testers with directed versions of known isoperimetric inequalities regarding the Boolean cube, linking directed versions of stronger inequalities with stronger bounds on the query copmplexity of such testers. Although I would have never presented the material in this way, I do apprecaite the nice manner in which the presentation progresses.

The original abstract

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.

See ECCC TR15-011.

Back to list of Oded's choices.