We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function \genf, where
\Sigma and \Xi are finite ordered sets, the test always accepts a
monotone f, and rejects f with high probability if it is \e-far
from being monotone (i.e., every monotone function differs from f on
more than an \e fraction of the domain). For any \e>0, the query
and time complexities of the test
are O((n/\e) \cdot \log |\Sigma|\cdot \log |\Xi|).
The previous best known bound
was \tildeO((n^2/\e) \cdot |\Sigma|^2 \cdot|\Xi|).
We also present an alternative test for the boolean range
\Xi=\bitset whose complexity is independent of
alphabet size |\Sigma|.
This test has query complexity O((n/\e) \log^2(n/\e)) and time
complexity O((n/\e) \log^3(n/\e)).

We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function f, where
\Sigma and \Xi are finite ordered sets, the test always accepts a
monotone f, and rejects f with high probability if it is \e-far
from being monotone (i.e., every monotone function differs from f on
more than an \e fraction of the domain). For any \e>0, the query
complexity of the test
is O((n/\e) \cdot \log |\Sigma|\cdot \log |\Xi|).
The previous best known bound
was \tildeO((n^2/\e) \cdot |\Sigma|^2 \cdot|\Xi|).
We also present an alternative test for the boolean range
\Xi=\bitset whose query complexity O(n^2/\e^2) is independent of
alphabet size |\Sigma|.