Testing monotonicity (Q5932642)

This paper provides a valuable nontrivial contribution to the area of learning and to the study of the power of randomisation. The following task is considered. Given a Boolean function \(f\), one has to decide whether \(f\) is monotone or far from being monotone (it differs by more than on a \(c\) fraction of inputs from any monotone function). The algorithm may ask for the values of the function on arguments of its choice and its complexity is measured in the number of queries. The author designed a randomized algorithm that (i) accepts every monotone function with certaincy, (ii) rejects every function with distance c from any monotone function with probability at least \(2/3\), and (iii) uses a number of queries that is linear in \(1/c\) and in the number of variables.