
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.
monotone Boolean functions, Analysis of algorithms and problem complexity, learning randomized algorithms, Randomized algorithms, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
monotone Boolean functions, Analysis of algorithms and problem complexity, learning randomized algorithms, Randomized algorithms, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 112 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
