Improved testing algorithms for monotonicity

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationRandomization, Approximation, and Combinatorial Optimization
Subtitle of host publicationAlgorithms 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
EditorsJose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen
PublisherSpringer Verlag
Pages97-108
Number of pages12
ISBN (Print)3540663290, 9783540663294
DOIs
StatePublished - 1999
Event3rd 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 1999Aug 11 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1671
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999
CountryUnited States
CityBerkeley
Period8/8/998/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

    Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., & Samorodnitsky, A. (1999). Improved testing algorithms for monotonicity. In J. D. P. Rolim, A. Sinclair, D. Hochbaum, & K. Jansen (Eds.), 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