# A o(n) monotonicity tester for Boolean functions over the hypercube

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2013.

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

- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)

## Abstract (arXiv)

A Boolean function f:0,1n mapsto 0,1 is said to be eps-far from monotone if f needs to be modified in at least eps-fraction of the points to make it monotone. We design a randomized tester that is given oracle access to f and an input parameter eps>0, and has the following guarantee: It outputs sf Yes if the function is monotonically non-decreasing, and outputs sf No with probability >2/3, if the function is eps-far from monotone. This non-adaptive, one-sided tester makes O(n7/8eps-3/2ln(1/eps)) queries to the oracle.