Adaptive Boolean Monotonicity Testing in Total Influence Time

Abstract

The problem of testing monotonicity of a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ has received much attention recently. Denoting the proximity parameter by $\epsilon$, the best tester is the non-adaptive $\tilde{O}(\sqrt{n}/{\epsilon }^2)$ 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({\epsilon }^{-1}\log n)$.

References in corpus (1)

• New algorithms and lower bounds for monotonicity testing