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

Deeparnab Chakrabarty, C. Seshadhri

A Boolean function $f:\{0,1{\}}^n\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. W…