Testing monotonicity

We present a. (randomized) test for monotonicity of Boolean functions. Name ly, given the ability to query an unknown function f:{0,1}(n) --> {0,1} at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is epsilon-far from being monotone (i.e., eve ry monotone function differs from f on more than an epsilon fraction of the domain). The complexity of the test is O(n/epsilon). The analysis of our algorithm relates two natural combinatorial quantities that can he measured with respect to a Boolean function; one being global t o the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions.