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 language | English (US) |
---|---|
Pages (from-to) | 1704-1717 |
Number of pages | 14 |
Journal | Information and Computation |
Volume | 204 |
Issue number | 11 |
DOIs | |
State | Published - 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