An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube

Authors:
  • DCD. Chakrabarty
    D. Chakrabarty
  • CSC. Seshadhri
    C. Seshadhri

Abstract
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.

This publication has 11 references indexed in Scilit: