An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
Deeparnab Chakrabarty, Comandur Seshadhri · SIAM Journal on Computing · 2016
A Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$ is said to be $\varepsilon$-far from monotone if $f$ needs to be modified in at least $\varepsilon$-fraction of the points to make it monotone. We design a randomized tester that is given oracle access to $f$ and an input parameter $\varepsilon>0$ and has the following guarantee: It outputs \sf Yes if the function is monotonically nondecreasing and outputs \sf No with probability $>2/3$, if the function is $\varepsilon$-far from monotone. This nonadaptive, one-sided tester makes $O(n^{7/8}\varepsilon^{-3/2}\ln(1/\varepsilon))$ queries to the oracle.