AN o(n) MONOTONICITY TESTER FOR BOOLEAN FUNCTIONS OVER THE HYPERCUBE

摘要

A Boolean function f : {0, 1}(n) -> {0, 1} is said to be epsilon-far from monotone if f needs to be modified in at least epsilon-fraction of the points to make it monotone. We design a randomized tester that is given oracle access to f and an input parameter epsilon > 0 and has the following guarantee: It outputs Yes if the function is monotonically nondecreasing and outputs No with probability > 2/3, if the function is epsilon-far from monotone. This nonadaptive, one-sided tester makes O(n(7/8)epsilon(-3/2) ln(1/epsilon)) queries to the oracle.