TY - GEN

T1 - Improved testing algorithms for monotonicity

AU - Dodis, Yevgeniy

AU - Goldreich, Oded

AU - Lehman, Eric

AU - Raskhodnikova, Sofya

AU - Ron, Dana

AU - Samorodnitsky, Alex

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f: Σn ↦ Ξ where Σ and Ξ are finite ordered sets, the test always accepts a monotone f, and rejects f with high probability if it is ϵ-far from being monotone (i.e., every monotone function differs from f on more than an _ fraction of the domain). For any ϵ > 0, the query complexity of the test is O((n=/ϵ) · log |Σ| · log | Ξ |). The previous best known bound was Õ ((n2/ϵ) ·|Σ|). We also present an alternative test for the boolean range Ξ = {0,1} whose query complexity O(n2/ϵ2) is independent of alphabet size |Σ|.

AB - We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f: Σn ↦ Ξ where Σ and Ξ are finite ordered sets, the test always accepts a monotone f, and rejects f with high probability if it is ϵ-far from being monotone (i.e., every monotone function differs from f on more than an _ fraction of the domain). For any ϵ > 0, the query complexity of the test is O((n=/ϵ) · log |Σ| · log | Ξ |). The previous best known bound was Õ ((n2/ϵ) ·|Σ|). We also present an alternative test for the boolean range Ξ = {0,1} whose query complexity O(n2/ϵ2) is independent of alphabet size |Σ|.

UR - http://www.scopus.com/inward/record.url?scp=84958773905&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958773905&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-48413-4_10

DO - 10.1007/978-3-540-48413-4_10

M3 - Conference contribution

AN - SCOPUS:84958773905

SN - 3540663290

SN - 9783540663294

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 108

BT - Randomization, Approximation, and Combinatorial Optimization

A2 - Rolim, Jose D. P.

A2 - Sinclair, Alistair

A2 - Hochbaum, Dorit

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999

Y2 - 8 August 1999 through 11 August 1999

ER -