# Approximating the Distance to Monotonicity of Boolean Functions

arXiv: https://arxiv.org/abs/1911.06924 · HTML: https://mlsanity.com/paper/1911.06924/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2019.

## Built on by (most cited first, 3 of 3)

- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Fast Agnostic Learners in the Plane](https://mlsanity.com/paper/2510.18057/) (2025)

## Abstract (arXiv)

We design a nonadaptive algorithm that, given oracle access to a function f: 0,1n → 0,1 which is α-far from monotone, makes poly(n, 1/α) queries and returns an estimate that, with high probability, is an widetildeO(√n)-approximation to the distance of 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/α)-query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant kappa > 0, every nonadaptive n1/2 - kappa-approximation algorithm for this problem requires 2n^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.