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