ECCC-Report TR99-017https://eccc.weizmann.ac.il/report/1999/017Comments and Revisions published for TR99-017en-usTue, 31 Aug 1999 00:00:00 +0300
Revision 1
| Improved Testing Algorithms for Monotonicity. Revision of: TR99-017 |
Yevgeniy Dodis,
Oded Goldreich,
Eric Lehman,
Sofya Raskhodnikova,
Dana Ron,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/1999/017#revision1
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))$.
Tue, 31 Aug 1999 00:00:00 +0300https://eccc.weizmann.ac.il/report/1999/017#revision1
Paper TR99-017
| Improved Testing Algorithms for Monotonicity. |
Yevgeniy Dodis,
Oded Goldreich,
Eric Lehman,
Sofya Raskhodnikova,
Dana Ron,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/1999/017
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|$.
Mon, 07 Jun 1999 10:38:57 +0300https://eccc.weizmann.ac.il/report/1999/017