A o(n) monotonicity tester for boolean functions over the hypercube
Given oracle access to a Boolean function f:{0,1}<sup>n</sup> -> {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(n<sup>5/6</sup>ε<sup>-5/3</sup>) queries to the oracle.