Information theory in property testing and monotonicity testing in higher dimension

Nir Ailon, Bernard Chazelle

Research output: Contribution to journalConference articlepeer-review

Abstract

In general property testing, we are given oracle access to a function f, and we wish to randomly 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 distance function. 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 property tester query complexity and we finetune the exponential dependence on the dimension d.

Original languageEnglish (US)
Pages (from-to)434-447
Number of pages14
JournalLECTURE NOTES IN COMPUTER SCIENCE
Volume3404
DOIs
StatePublished - 2005
Event22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005 - Stuttgart, Germany
Duration: Feb 24 2005Feb 26 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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