A o(n) monotonicity tester for boolean functions over the hypercube
Deeparnab Chakrabarty, Comandur Seshadhri · 2013
Given oracle access to a Boolean function f:{0,1}n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n5/6ε-5/3) queries to the oracle.