# Adaptive Boolean Monotonicity Testing in Total Influence Time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jan 2018.

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

- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)

## Abstract (arXiv)

The problem of testing monotonicity of a Boolean function f:0,1n → 0,1 has received much attention recently. Denoting the proximity parameter by varepsilon, the best tester is the non-adaptive widetildeO(√n/varepsilon2) tester of Khot-Minzer-Safra (FOCS 2015). Let I(f) denote the total influence of f. We give an adaptive tester whose running time is I(f)poly(varepsilon-1log n).