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|$.