We ended our last post discussing results from 2014 by discussing the monotonicity testing conjecture that \(O(\sqrt{n})\) queries suffice to test whether a Boolean function is monotone.  As it turns out, a proof of this conjecture was just around the corner…

On Monotonicity Testing and Boolean Isoperimetric type Theorems by Subhash Khot, Dor Minzer, and Muli Safra (ECCC). This remarkable paper shows that, indeed, we can test whether \(f : \{0,1\}^n \to \{0,1\}\) is monotone with \(O(\sqrt{n})\) queries using a natural tester. The authors establish this result by building on the connection between monotonicity testers and directed analogues of isoperimetric inequalities on the Boolean hypercube first established by Chakrabarty and Seshadhri. Specifically, the authors establish a directed analogue of a classic inequality of Talagrand and combine it with a number of other interesting innovations to analyze their monotonicity tester.

Big Data on the Rise: Testing monotonicity of distributions by Clément Canonne (arXiv). Another setting in which monotonicity testing has received a lot of attention recently is in the setting of testing properties of distributions. A distribution \(D\) on \(\{1,2,\ldots,n\}\) is monotone (non-increasing) if its probability mass function is non-increasing: \(D(1) \ge D(2) \ge \cdots \ge D(n)\). When we must test whether a function is monotone by drawing samples from the distribution, \(\tilde{\Theta}(\sqrt{n})\) samples are both necessary and sufficient. This work shows that, in contrast, testers with stronger query access (such as conditional sampling) to the distribution can test monotonicity much more efficiently.