Information theory in property testing and monotonicity testing in higher dimension

Nir Ailon, Bernard Chazelle

Research output: Contribution to journalArticle

43 Scopus citations

Abstract

In property testing, we are given oracle access to a function f, and we wish to test if the function satisfies a given property P, or it is ε-far from having that property. In a more general setting, the domain on which the function is defined is equipped with a probability distribution, which assigns different weight to different elements in the domain. This paper relates the complexity of testing the monotonicity of a function over the d-dimensional cube to the Shannon entropy of the underlying distribution. We provide an improved upper bound on the query complexity of the property tester.

Original languageEnglish (US)
Pages (from-to)1704-1717
Number of pages14
JournalInformation and Computation
Volume204
Issue number11
DOIs
StatePublished - Nov 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Information theory
  • Property testing

Fingerprint Dive into the research topics of 'Information theory in property testing and monotonicity testing in higher dimension'. Together they form a unique fingerprint.

  • Cite this