Revision #1 Authors: Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Accepted on: 31st August 1999 00:00

Downloads: 2501

Keywords:

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

TR99-017 Authors: Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Publication: 7th June 1999 10:38

Downloads: 2176

Keywords:

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