Approximating the Distance to Monotonicity of Boolean Functions

We design a nonadaptive algorithm that, given oracle access to a function $f: {0,1}^n \to {0,1}$whichis$\alpha$-farfrommonotone,makespoly$(n, 1/\alpha)$queriesandreturnsanestimatethat,withhighprobability,isan$\widetilde{O}(\sqrt{n})$-approximationtothedistanceof$f$ to monotonicity. The analysis of our algorithm relies on an improvement to the directed isoperimetric inequality of Khot, Minzer, and Safra (SIAM J. Comput., 2018). Furthermore, we rule out a poly$(n,1\mathrm{/}\alpha )$-query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant $\kappa >0,$ every nonadaptive $n^{1/2 - \kappa}$-approximationalgorithmforthisproblemrequires$2^{n^\kappa}$ queries. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. We obtain our lower bound by proving an analogous bound for erasure-resilient (and tolerant) testers. Our method also yields the same lower bounds for unateness and being a $k$-junta.