Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR99-017 | 31st August 1999 00:00

Improved Testing Algorithms for Monotonicity. Revision of: TR99-017

RSS-Feed

Abstract:


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


Paper:

TR99-017 | 4th June 1999 00:00

Improved Testing Algorithms for Monotonicity.


Abstract:


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



ISSN 1433-8092 | Imprint