### Abstract

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 Õ ((n^{2}/ϵ) ·|Σ|). We also present an alternative test for the boolean range Ξ = {0,1} whose query complexity O(n^{2}/ϵ^{2}) is independent of alphabet size |Σ|.

Original language | English (US) |
---|---|

Title of host publication | Randomization, Approximation, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 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, Proceedings |

Editors | Jose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen |

Publisher | Springer Verlag |

Pages | 97-108 |

Number of pages | 12 |

ISBN (Print) | 3540663290, 9783540663294 |

DOIs | |

State | Published - 1999 |

Event | 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 - Berkeley, United States Duration: Aug 8 1999 → Aug 11 1999 |

### Publication series

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

Volume | 1671 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 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 |
---|---|

Country | United States |

City | Berkeley |

Period | 8/8/99 → 8/11/99 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Improved testing algorithms for monotonicity'. Together they form a unique fingerprint.

## Cite this

*Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 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, Proceedings*(pp. 97-108). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1671). Springer Verlag. https://doi.org/10.1007/978-3-540-48413-4_10