Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

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

Revision #1
Authors: Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
Accepted on: 31st August 1999 00:00
Keywords:

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.

TR99-017
Authors: Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
Publication: 7th June 1999 10:38
Keywords:

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