zbMATH — the first resource for mathematics

Testing monotonicity. (English) Zbl 0964.68148
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.

68W20 Randomized algorithms
68Q25 Analysis of algorithms and problem complexity
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI